사과나무 C++ - 백준 2987

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

문제 접근

어떤 점 하나가 $\triangle ABC$에 속한다는 것을 생각해보았다.

삼각형 위의 점 $A,B,C$에 대하여 시계방향, 반시계방향을 따졌을 때

$A$보다 $X$좌표가 크거나 같거나, $Y$좌표가 크거나 같거나....

를 따지면 된다고 생각했다.

이때 한가지 더 떠오른 것이 있는데

각 변에 대하여 어떤 점 하나와 ccw를 돌려주는 것이다.

그러면 어떤 점이 그 변에 대하여 위쪽, 아래쪽에 있는 것을 확인할 수 있고,

$\triangle ABC$의 넓이보다 큰지 작은지도 알 수 있을 것이다.

이를 하나하나 따져보면 다음과 같다.

만약 $\triangle ABC$의 ccw가 음수, 양수일 때 어떤 점 $x$에 대하여 나타낸 그림이다.

위 조건을 구현한 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

struct pos{
    int x,y;
};

double getCCW(pos a, pos b, pos c){
    return a.x*b.y+b.x*c.y+c.x*a.y-(b.x*a.y+c.x*b.y+a.x*c.y);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,ans=0;
    pos A,B,C,tmp;
    cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y >> n;
    double area=getCCW(A,B,C),ccw;
    for(int i=0;i<n;i++){
        cin >> tmp.x >> tmp.y;
        if(area<0){
            ccw=getCCW(A,tmp,B);
            if(abs(ccw)>-area) continue;
            if(ccw<0) continue;
            ccw=getCCW(B,tmp,C);
            if(abs(ccw)>-area) continue;
            if(ccw<0) continue;
            ccw=getCCW(C,tmp,A);
            if(abs(ccw)>-area) continue;
            if(ccw<0) continue;
            ans++;
        }
        else{
            ccw=getCCW(A,tmp,B);
            if(abs(ccw)>area) continue;
            if(ccw>0) continue;
            ccw=getCCW(B,tmp,C);
            if(abs(ccw)>area) continue;
            if(ccw>0) continue;
            ccw=getCCW(C,tmp,A);
            if(abs(ccw)>area) continue;
            if(ccw>0) continue;
            ans++;
        }
    }
    cout << fixed;
    cout.precision(1);
    cout << abs(area)/2 << '\n' << ans;
    return 0;
}