[BOJ/Gold 4] 백준 2987 사과나무(C++)

문제 링크

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

 

문제

백준이는 사과나무가 N개 심어져있는 땅의 일부를 구매했다. 백준이가 구매한 땅은 삼각형이다. 따라서, 어떤 사과나무가 백준이의 것인지 알기가 힘들었다.

백준이 땅의 꼭짓점 좌표와 사과나무의 좌표가 주어졌을 때, 백준이 땅의 넓이와 백준이의 사과나무의 개수를 구하는 프로그램을 작성하시오.

만약, 어떤 사과나무가 땅의 경계선에 걸쳐있다면, 이것은 백준이 사과나무이다.

(xA, yA), (xB, yB), (xC, yC) 로 이루어진 삼각형의 넓이는 다음과 같이 구할 수 있다.

|xA(yB - yC) + xB(yC - yA) + xC(yA - yB)| / 2

 

입력

처음 세 개의 줄은 삼각형의 꼭짓점 좌표이다. 다음 줄에는 사과나무의 개수 N이 주어진다. (1 ≤ N ≤ 100). 다음 N개의 줄에는 사과나무의 좌표가 주어진다.

모든 좌표는 1,000보다 작거나 같은 양의 정수이고, 공백으로 구분되어져 있다.

 

출력

첫째 줄에는 백준이 땅의 넓이를 소수점 첫째자리까지 출력하고, 둘째 줄에는 백준이의 사과나무 개수를 출력한다.

 

예제 입력 1

1 1
5 1
3 3
4
3 1
3 2
3 3
3 4

예제 출력 1

4.0
3

예제 입력 2

3 2
5 4
1 6
3
2 4
3 5
4 3

예제 출력 2

6.0
3

예제 입력 3

2 6
5 1
7 8
5
1 4
3 5
6 4
6 5
4 7

예제 출력 3

15.5
2

 

알고리즘 분류

• 기하학

 

풀이

먼저 삼각형의 꼭짓점 3개를 반시계 방향으로 정렬한다.

반시계 방향으로 정렬하는 법은, 정렬된 꼭짓점 3개의 외적을 구해서 외적이 0 미만이면 시계 방향으로 정렬되어 있는 것이기 때문에 1번째 점과 2번째 점을 맞바꾼다.(0이면 삼각형이 구성되지 않으므로 제외)

그리고 문제에 주어진 대로 삼각형의 넓이를 구하고, 소숫점 둘째 자리에서 반올림한다.

이제 N개의 점을 입력받으면서 해당 점이 삼각형 안에 존재하는지를 판별하는데, 역시 여기서도 외적을 사용한다.

외적이 0 이상이면 삼각형 안이나 경계에 존재하는 것이며, 모든 점과의 외적을 구해서 판단해야 하기 때문에 총 3번 외적을 계산한다.

한 번이라도 외적이 0 미만이면 해당 점은 삼각형 바깥에 존재하는 것이다.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

using namespace std;
vector<pair<double, double> > Triangle(3);
int N;
double X, Y;
double AnswerA;
int AnswerB;

double getCCW(pair<double, double> A, pair<double, double> B, pair<double, double> C) {
    return ((A.first * B.second) + (B.first * C.second) + (C.first * A.second) - (A.second * B.first) - (B.second * C.first) - (C.second * A.first));
}

void settings() {
    bool Flag = true;
    for (int i = 0; i < 3; i++) {
        pair<double, double> Now = Triangle[i];
        pair<double, double> Next = Triangle[(i + 1) % 3];
        double NowCCW = getCCW(Now, Next, make_pair(X, Y));
        if (NowCCW < 0) {
            Flag = false;
            break;
        }
    }
    
    if (Flag) {
        AnswerB++;
    }
}

void input() {
    for (int i = 0; i < 3; i++) {
        cin >> Triangle[i].first >> Triangle[i].second;
    }
    if (getCCW(Triangle[0], Triangle[1], Triangle[2]) < 0) {
        swap(Triangle[1], Triangle[2]);
    }
    double XA = Triangle[0].first;
    double YA = Triangle[0].second;
    double XB = Triangle[1].first;
    double YB = Triangle[1].second;
    double XC = Triangle[2].first;
    double YC = Triangle[2].second;
    AnswerA = abs(XA * (YB - YC) + XB * (YC - YA) + XC * (YA - YB)) / (double) 2;
    AnswerA *= 10;
    AnswerA = floor(AnswerA);
    AnswerA /= 10;
    
    cin >> N;
    while (N--) {
        cin >> X >> Y;
        settings();
    };
}

void print_Answer() {
    cout << fixed;
    cout.precision(1);
    cout << AnswerA << "\n";
    cout << AnswerB << "\n";
}

int main() {
    FASTIO
    input();
    print_Answer();

    return 0;
}