| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 1202 | 373 | 250 | 28.153% |
문제
소들의 반란이 있은 뒤, 이 소들은 포로로 잡은 인간들을 감시해야 했다.
소들은 (Px, Py)의 위치에 감옥을 짓고, 감옥 둘레에 가능한 한 여러 겹으로 담을 쌓아 포로들이 도망가기 힘들도록 하려 한다. 감옥은 하나의 점으로 표현된다.
이러한 목적을 달성하기 위해, 소들은 감옥 주변에 N개의 담 기둥을 세웠다. 각각의 담은 감옥을 완전히 감싸야 하고, 담 안에 (부분적으로라도) 포함되는 담이 있다면 이러한 담도 완전히 감싸야 한다. 즉, 담벼락이 교차하거나 한 점에서 만나서는 안 된다. 감옥과 담 기둥 중 어느 세 점도 일직선상에 있지 않다.
이러한 담 기둥들이 주어졌을 때, 겹치지 않는 최대의 중첩된 담의 겹 수를 구하는 프로그램을 작성하시오.
담은 여러 개의 담벼락이 연결된, 닫힌 다각형을 의미하고, 각각의 담벼락의 두 끝 점은 담 기둥 이어야 한다. 이러한 담 사이에는 반드시 약간이라도 공간이 있어야 한다. 즉, 서로 다른 두 담이 하나의 담벼락이나 담 기둥을 공유해서는 안 된다.
입력
첫째 줄에 N(1≤N≤1,000), Px, Py (-100,000≤Px, Py≤100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다.
출력
첫째 줄에 최대 겹 수를 출력한다.
접근
Convex Hull 개념을 이미 알고 있기에, 외곽부터 Convex Hull을 씌워가면서 몇 겹인지 계산하면 되겠다는 생각이 바로 들었다.
다만, 이 Convex Hull 내부에 감옥이 있는지를 판단하는 것도 중요하다.
여기에는 CCW 기법을 사용했다. (물론 Convex Hull에도 CCW가 들어간다.)
만약 Convex Hull 내부에 감옥이 있다면
(감옥, first, second) 의 CCW는 무조건 시계방향이다.
따라서, CCW가 달라지는 구간이 생긴다면 감옥이 담벼락의 외부에 있는 것이다.
Convex Hull에 해당하는 좌표를 기존 벡터에서 지워가면서 반복 진행하면 정답이 나온다.
풀이
구현하기가 생각보다 까다로웠다.
모두 함수화하여 반복하기 편하게 구현했다.
convex_hull 함수에서 convex hull 과정을 진행해주고,
이 좌표들이 감옥을 감싸고 있는지 확인해주었다.
만약 아닌 경우는 false를 반환하여 반복한 횟수를 바로 출력했다.
그리고 set를 활용해서 기존 벡터인 v에서 좌표들을 지워주었다.
ccw를 int로 구현하여 오버플로우가 발생해서 많은 시간을 날렸다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
#define MAX 1000
struct Point
{
int x, y, p, q;
Point(int _x = 0, int _y = 0) : x(_x), y(_y), p(1), q(0) {}
bool operator==(Point& A)
{
return (x == A.x) && (y == A.y);
}
};
bool comp(const Point & A, const Point & B)
{
if (1LL * A.q * B.p != 1LL * A.p * B.q)
return 1LL * A.q * B.p < 1LL * A.p * B.q;
if (A.y != B.y)
return A.y < B.y;
return A.x < B.x;
}
int ccw(const Point & A, const Point & B, const Point & C)
{
ll tmp = (1LL * A.x * B.y + 1LL * B.x * C.y + 1LL * C.x * A.y - 1LL * B.x * A.y - 1LL * C.x * B.y - 1LL * A.x * C.y);
if (tmp > 0) return 1;
else if (tmp == 0) return 0;
else return -1;
}
int N, x, y, px, py, ans = 0;
bool ok = true;
vector<Point> v;
Point P;
void input()
{
CIN3(N, px, py);
P = Point(px, py);
v.resize(N);
FUP(i, 0, N - 1)
{
CIN2(x, y);
v[i] = Point(x, y);
}
}
bool convex_hull(vector<Point> arr)
{
int n = arr.size();
if (n < 3) return false;
sort(ALL(arr), comp); // y좌표, x좌표가 작은 순으로 정렬
FUP(i, 1, n - 1) // 기준점으로부터 상대 위치 계산
{
arr[i].p = arr[i].x - arr[0].x;
arr[i].q = arr[i].y - arr[0].y;
}
auto it = arr.begin();
it++;
sort(it, arr.end(), comp); // 반시계 방향으로 다시 정렬
stack<int> S;
S.push(0);
S.push(1);
int next = 2;
while (next < n)
{
while (S.size() >= 2)
{
int first, second;
second = S.top();
S.pop();
first = S.top();
// first, second, next가 좌회전 ( > 0 )이라면 second push
// 우회전( < 0 )이라면 위의 while문 계속 반복
if (ccw(arr[first], arr[second], arr[next]) > 0)
{
S.push(second);
break;
}
}
// next push
S.push(next++);
}
if (S.size() < 3) return false;
set<int> have;
int first = S.top(); S.pop();
int start = first;
int second = S.top(); S.pop();
have.insert(first); have.insert(second);
int direct = ccw(arr[first], arr[second], P);
while (!S.empty())
{
first = second;
second = S.top();
have.insert(second);
S.pop();
if (direct != ccw(arr[first], arr[second], P)) return false;
}
if (direct != ccw(arr[second], arr[start], P)) return false;
vector<Point> newV;
FUP(i, 0, n - 1)
{
if (!have.count(i))
{
newV.push_back(arr[i]);
}
}
v = newV;
ans++;
return true;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
while (convex_hull(v)) {}
COUT(ans);
return 0;
}