백준 18032 - Dazzling Stars

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

18032번: Dazzling Stars

 

[알고리즘 분류]

정렬

기하학

 어떤 두 점의 방향성이 정해졌다면, 인쇄 방향은 저 파란색 부분의 각도에 들어있어야 한다. 즉, 다른 점들의 방향이 모두 저 범위에 들어있어야 한다. 모든 방향을 각도 순으로 정렬하고, 원형 스위핑을 하자. 한 번이라도 현재 방향과 이전 방향의 차이가 180도 이상이 된 적이 있다면 답이 존재한다.

 CCW는 0도, 180도 두 경우 모두 0을 반환하기 때문에, 이를 따로 구별해줘야 한다.

#include <algorithm>
#include <vector>
#include <iostream>
 
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
 
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define X first
#define Y second
#define endl '\n'
 
 
struct Point {
    ll x, y, c;
    Point() {}
    Point(ll x, ll y, ll c) : x(x), y(y), c(c) {}
};
 
vector<Point> inp;
vector<pll> v;
 
ll ccw(pll p1, pll p2) {
    ll ret = p1.X * p2.Y - p2.X * p1.Y;
    if (ret == 0) {
        if (p1.X * p2.X < 0 || p1.Y * p2.Y < 0) return 0;
        return 1;
    }
    if (ret > 0) return 1;
    return -1;
}
 
bool cmp(const pll p1, const pll p2) {
    if ((p1.X < 0) != (p2.X < 0)) {
        return p1.X < p2.X;
    }
    return p1.Y * p2.X < p1.X * p2.Y;
}
 
 
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        ll x, y, c; cin >> x >> y >> c;
        inp.emplace_back(x, y, c);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (inp[i].c < inp[j].c) {
                v.emplace_back(inp[j].x - inp[i].x, inp[j].y - inp[i].y);
            }
        }
    }
    sort(v.begin(), v.end(), cmp);
    n = v.size();
    bool fl = false;
    for (int i = 0; i < n * 2; i++) {
        if (ccw(v[i % n], v[(i + 1) % n]) <= 0) fl = true;
    }
    if (n == 0) {
        cout << "Y";
    }
    else {
        if (fl) {
            cout << "Y";
        }
        else {
            cout << "N";
        }
    }
 
    return 0;
}