기하

 

CCW(Counter Clock-Wise)

이론적으로는 외적을 구하는것 같은데, 알고리즘 기하문제를 풀기위해 사용한다. 

 

용도1. 다각형 면적구하기

점3개를 주면 꼭지점 3개로 해석해 면적을 구해준다. (정확히는 평행사변형의 면적을 주는건데 삼각형의 면적이 더 유용해서 2로 나눠서 쓴다)

이걸 사용하면 도형의 외각선 좌표들이 순서대로 주어질때 아래처럼 삼각형으로 쪼개면 다각형의 면적을 구할 수 있다.

 

점 3개가 순서대로 반시계 방향을 이루면 +값을 가지고 시계방향을 이루면 -값을 가진다. (오른손 법칙을 떠올리면 좋다)따라서 최종결과에 절대값을 씌워야 할 수 있다.

 

재밌는 점은 아래와 같은 볼록다각형에 대해서도 자동으로 삭감이 이루어지면서 면적계산이 제대로 된다는 점이다.

 

 

내 소스는 다음과 같다. 이 문제의 답안이기도 하다.

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
 
struct point { int x, y; };
double CCW(point A, point B, point C) {
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
 
int32_t main()
{
    vector<point> v;
    int N, x, y; cin >> N; REP(i, N)cin >> x >> y, v.push_back({ x,y });
 
    double sum = 0;
    for (int i = 1; i < N-1; i++) {
        sum += CCW(v[0], v[i], v[i + 1]);
    }
    cout.precision(1);
    cout << fixed << (double)abs(sum)/2 <<'\n';
    return 0;
}

 

용도2. 점 3개의 방향성 구하기

위에서 반시계 방향일때 CCW가 +값을 리턴한다고 했는데 +,0,-를 이용해서 방향성을 판단할 수 있다는 것. 아래 선분교차 판단 등에 쓰인다.

 

용도3. 선분교차 판단

여기에 설명 잘 나와있어서 보고 이해하면 될 것 같다.

주의할점은 CCW를 1,0,-1을 리턴하는 것으로 변경하지 않으면 long long을 사용해도 오버플로가 날 수 있다는 점이다(아래코드 보면 CCW간 곱셈이 들어가서..)

아래코드를 나중에 활용하자. 이 문제의 답안이기도 하다.

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
 
struct point { double x, y; };
double CCW(point A, point B, point C, bool sign_only=true) {
    double r = (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
    if (sign_only == false) return r;
    if (r == 0)return 0;
    return r > 0 ? 1 : -1;
}
struct line { point s, e; };
//touch_ok가 false이면, 두 선분이 교차하지 않고 만나기만 하는 경우에는 false를 리턴
bool Intersect(line x, line y, bool touch_ok=false) {
    point a = x.s, b = x.e;
    point c = y.s, d = y.e;
    double ab = CCW(a, b, c) * CCW(a, b, d);
    double cd = CCW(c, d, a) * CCW(c, d, b);
    if (ab == 0 && cd == 0) { // 이건 두 선분이 평행한 경우
        pair<double, double> aa = { a.x, a.y }, bb = { b.x,b.y }, 
            cc = { c.x, c.y }, dd = { d.x,d.y };
        if (aa > bb)swap(aa, bb);
        if (cc > dd)swap(cc, dd);
        if(touch_ok) return cc <= bb && aa <= dd; // 0이면 점끼리 만나는 것
        return cc < bb && aa < dd; // a<d이면서 b,c가 교차하면 선분
    }
    if(touch_ok) return ab <= 0 && cd <= 0; // 0이면 두 선분이 한점에서 만나는 것
    return ab < 0 && cd < 0; // 이게 기본. 각선분에서 나머지 2개점 방향이 달라야 교차
}
 
int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
#endif
 
    vector<line> l;
    double a, b, c, d; REP(i, 2)cin >> a >> b >> c >> d, l.push_back({ a,b,c,d });
    cout << (Intersect(l[0],l[1])?1:0) <<'\n';
    return 0;
}