백준: Class 5 - 17386, 17387, 20149(CCW, Signed Area, 선분 교차 1, 2, 3)

</br> 선분 교차 2가 클래스 5에 있길래 다른 애들도 풀어 봅시다
</br>

CCW, Signed Area

int sarea(long long x1,long long y1,
          long long x2,long long y2,
          long long x3, long long y3){
    if( x2*y1 + x3*y2 + x1*y3 - (x1*y2 + x2*y3 + x3*y1) < 0 ) return 1;
    return -1;
}

다른 데선 보통 CCW로 부르던데 알고리즘 때 signed area라 배웠더니 나는 이게 더 착착 붙는다
한 선분에서 점이 어느쪽에 있는 지를 알 수 있다.
</br>

17386: 선분 교차 1

https://www.acmicpc.net/problem/17386

    long long sarea1 = sarea(x1,y1, x2,y2, x3,y3);
    long long sarea2 = sarea(x1,y1, x2,y2, x4,y4);
    long long sarea3 = sarea(x3,y3, x4,y4, x1,y1);
    long long sarea4 = sarea(x3,y3, x4,y4, x2,y2);

    if( sarea1*sarea2 <= 0 && sarea3*sarea4 <= 0 ) cout << 1 << endl;
    else cout << 0 << endl;

세 점이 일직선 위 있는 경우가 없는 문제다.
각 직선에서 다른 두 점을 향한 값을 구하고, 그 둘의 부호가 다르면 교차한다.
</br>

int sarea(pair<long long, long long> &a,
          pair<long long, long long> &b,
          pair<long long, long long> &c){
    long long x1 = a.first;
    long long y1 = a.second;
    long long x2 = b.first;
    long long y2 = b.second;
    long long x3 = c.first;
    long long y3 = c.second;
    long long ret = x2*y1 + x3*y2 + x1*y3 - (x1*y2 + x2*y3 + x3*y1);
    if( ret < 0 ) return 1;
    if( ret == 0 ) return 0;
    return -1;
}

    pair<long long, long long> a, b, c, d;
    cin >> a.first>>a.second >> b.first>>b.second;
    cin >> c.first>>c.second >> d.first>>d.second;

좌표 관리하기 귀찮으니까 페어로 해 봅시다
그리고 0인 경우, 즉 같은 직선 위에 있는 경우가 선분 교차 2에서 추가 되었기 때문에 넣어주자.
</br>

17387: 선분 교차 2

https://www.acmicpc.net/problem/17387

    long long abc = sarea(a, b, c);
    long long abd = sarea(a, b, d);
    long long cda = sarea(c, d, a);
    long long cdb = sarea(c, d, b);

    if( abc*abd <= 0 && cda*cdb <= 0 ){
        if( abc*abd == 0 && cda*cdb == 0 ){
            if( a > b ) swap(a, b);
            if( c > d ) swap(c, d);
            if( a <= d && c <= b ) cout << 1 << endl;
            else cout << 0 << endl;
        }
        else cout << 1 << endl;
    }
    else cout << 0 << endl;

0인 경우 같은 직선 위에 있다.

A----C---B---D

A < B, C < D라고 가정하면, A < D이고 C < B일 때 교차한다.
</br>

20149: 선분 교차 3

https://www.acmicpc.net/problem/20149

교차하는 좌표 구하기

ax + by = c
dx + ey = f
라고 하면
각 좌표를 대입해서
a = (y2-y1)/(x1-x2);
b = 1;
c = (y1*x2 - y2*x1)/(x2-x1);

d = (y4-y3)/(x3-x4);
e = 1;
f = (y3*x4 - y4*x3)/(x4-x3);
를 구할 수 있다.

따라서 교차하는 점은
ansx = (c*e - b*f)/(a*e - b*d);
ansy = (c*d - a*f)/(b*d - a*e); 인데
정리하면
ansx = (c - f)/(a - d);
ansy = (c*d - a*f)/(d - a);

ansx = {(x1*y2-y1*x2)*(x3-x4) - (x3*y4-y3*x4)*(x1-x2)} / {(x1-x2)*(y3-y4) - (y1-y2)*(x3-x4)}
ansy = {(x1*y2-y1*x2)*(y3-y4) - (x3*y4-y3*x4)*(y1-y2)} / {(x1-x2)*(y3-y4) - (y1-y2)*(x3-x4)}

즉
ansxx = (x1*y2-y1*x2)*(x3-x4) - (x3*y4-y3*x4)*(x1-x2)
ansyy = (x1*y2-y1*x2)*(y3-y4) - (x3*y4-y3*x4)*(y1-y2)
t = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4)

ansx = ansxx/t
ansy = ansyy/t

나눗셈을 하면 부정확해지므로 식을 어떻게든 정리하는 게 중요하다…

</br>

코드

void func(pair<ll, ll> &a,
          pair<ll, ll> &b,
          pair<ll, ll> &c,
          pair<ll, ll> &d){
    ll x1 = a.first;
    ll y1 = a.second;
    ll x2 = b.first;
    ll y2 = b.second;
    ll x3 = c.first;
    ll y3 = c.second;
    ll x4 = d.first;
    ll y4 = d.second;

    long double ansxx = (x1*y2-y1*x2)*(x3-x4) - (x3*y4-y3*x4)*(x1-x2);
    long double ansyy = (x1*y2-y1*x2)*(y3-y4) - (x3*y4-y3*x4)*(y1-y2);
    long double t = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);

    if( t == 0 ){
        if( b == c && a <= c ) cout << x2 << ' '<< y2 << endl;
        else if( a == d && c <= a ) cout << x1 << ' '<< y1 << endl;
        return;
    }
    long double ansx = ansxx/t;
    long double ansy = ansyy/t;
    cout << ansx << ' ' << ansy << endl;
}

// in main()
    if( a > b ) swap(a, b);
    if( c > d ) swap(c, d);

    ll abc = sarea(a, b, c);
    ll abd = sarea(a, b, d);
    ll cda = sarea(c, d, a);
    ll cdb = sarea(c, d, b);

    if( abc*abd <= 0 && cda*cdb <= 0 ){
        if( abc*abd == 0 && cda*cdb == 0 ){
            if( a <= d && c <= b ){
                cout << 1 << endl;
                func(a, b, c, d);
            }
            else cout << 0 << endl;
        }
        else{
            cout << 1 << endl;
            func(a, b, c, d);
        }
    }
    else cout << 0 << endl;

저 t가 0이면 nan이 되기 때문에, 따로 처리해 준다. 0이면 평행하는 경우다.
위 선분 교차 2의 코드에서, 1일 때 교차점 출력하는 코드만 붙였다.
</br>

---

복잡하구나
기하 문제를 별로 안 푼 것 같다
</br>