白駿17387号:線分交差2

12614 ワード
geometry ps cpp テキストリンク

線分の交差2


白駿17387号:線分交差2

アイデア


ベクトルの外在的な意味は誰が知っていますか?
反時計回り(CCW)、外積正、時計回り負、直線0

これで線分が交差しているかどうかを知ることができます.どうしよう.

p 1(x 1,y 1)p 2(x 2,y 2)/p 3(x 3,y 3)p 4(x 4,y 4)のように2つの線分がある場合、ccw(p 1,p 2,p 3)*ccw(p 1,p 2,p 4)の値とccw(p 3,p 4,p 1)*ccw(p 3,p 4,p 2)の値のどちらも交差しない.
しかし、例外もある.4つの点が一直線上にあるときです.(1、1)(2、2)/(3、3)(4、4)の2つのセグメントは交差しないが、ccwに乗じた値はいずれも0である.

サイズ関係を比較するために、p 1、p 3に小さな値を加えてswapを行い、真ん中に重なる部分があるかどうかをチェックして交差するかどうかを決定します.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

int ccw(long long x1, long long y1, long long x2, long long y2, long long x3, long long y3) {
    long long temp = x1*y2+x2*y3+x3*y1;
    temp = temp - y1*x2-y2*x3-y3*x1;
    if (temp > 0) {
        return 1;
    } 
    else if (temp < 0) {
        return -1;
    } 
    else {
        return 0;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    long long x1, y1, x2, y2, x3, y3, x4, y4;
    cin >> x1 >> y1 >> x2 >> y2;
    cin >> x3 >> y3 >> x4 >> y4;
    
    int ccw1 = ccw(x1, y1, x2, y2, x3, y3);
    int ccw2 = ccw(x1, y1, x2, y2, x4, y4);
    int ccw3 = ccw(x3, y3, x4, y4, x1, y1);
    int ccw4 = ccw(x3, y3, x4, y4, x2, y2);
    
    pair<long long, long long> p1 = {x1, y1};
    pair<long long, long long> p2 = {x2, y2};
    pair<long long, long long> p3 = {x3, y3};
    pair<long long, long long> p4 = {x4, y4};
    
    bool s1 = (ccw1*ccw2<=0);
    bool s2 = (ccw3*ccw4<=0);
        
    if (ccw1*ccw2 == 0 && ccw3*ccw4 == 0) {
        if (p1 > p2) {
            swap(p1, p2);
        }
        if (p3 > p4) {
            swap(p3, p4);
        }
        if (p2 < p3 || p1 > p4) {
            s1 = false;
        }
    }
    cout << (s1&&s2);
    return 0;
}

おしゃべり


生まれて初めて幾何学の問題をする.心配事が多い.順番、オーバーフローに気をつけて!
点対点関係比較でx値が同じ場合はy値で比較する必要があるのでpairに直接入れて自動比較する.
正解率はますます高くなっている.
[SpringbootとJPA 1を活用]2プロジェクトの環境設定
Qt学習ノート:QTimerとQTime