레야몬

1. 문제 두 원이 주어졌을 때, 교차하는 영역의 넓이를 소수점 셋째 자리까지 구하시오. - 1 - 두 원의 중심과 반지름 \(x_{1}, y_{1}, r_{1}, x_{2}, y_{2}, r_{2}\) 실수는 최대 소수점 둘째자리까지 구한다 - 1 - 교차하는 영역의 넓이를 반올림해 소수점 셋째 자리까지 출력한다. 2. 재정의 X 3. 해결 방법 두 점 사이의 거리 \(d = \sqrt{(x_{2} - x_{1})^{2} + (y_{2} - y_{1})^{2}}\) 코사인 제2법칙 \(x^{2} + y^{2} - 2xycos(\theta) = z^{2}\) 사인 법칙 \(S = \frac{1}{2} absin(\theta)\) 4. 실수한 점, 개선한 점 X #include #include using ..

1. 문제 N개의 선분들이 2차원 평면상에 주어져 있다. 두 선분이 서로 만나는 경우에 두 선분은 같은 그룹에 속했다고 하며 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 이 N개의 선분들은 몇 개의 그룹으로 되어있을까? 또, 가장 큰 그룹에 속하는 선분의 개수는 몇 개인가? - 1 - \(N(1 \leq N \leq 3,000)\) - N개의 줄 - 선분의 양 끝점의 좌표 \(\left|x_{i} \right|, \left|y_{i} \right| \leq 5,000\) - 1 - 그룹의 수 - 2 - 가장 크기가 큰 그룹에 속한 선분의 개수 2. 재정의 선분 그룹 개수와 그 크기 구하기 3. 해결 방법 N*N = 9,000,000으로 CCW를 이용해 선분 교차를 모두 파악하고 이를 union..

1. 문제 2차원 좌표 평면 위 두 선분 \(L_{1}, L_{2}\)가 주어졌을 때 두 선분의 교차 여부를 판단하자. 한 선분의 각 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. - 1 - \(x_{1}, y_{1}, x_{2}, y_{2}\) - 2 - \(x_{3}, y_{3}, x_{4}, y_{4}\) \((-1,000,000 \leq x_{i}, y_{i} \leq 1,000,000), (x_{i}, y_{i} \in \mathbb{Z}), (0 < l_{1}, l_{2})\) - 1 - 교차하면 1, 아니면 0을 출력 - 2 - 교차하는 점의 x좌표와 y좌표 출력 2. 재정의 교차점 구하기 3. 해결 방법 CCW로 적절히 하면 되는데 너무 조건 분기가 많아서 생략하고 아래 링크..

1. 문제 n개의 도시를 가진 나라가 있다. 이 나라의 도시 중 가장 먼 두 도시를 찾아 그 도시의 좌표를 구하라. 단 모든 도시는 한 평면 위에 있다. -1- 테스트 케이스의 수 T --1- 도시의 개수 \(n(2 \leq n \leq 200,000)\) --n개- x좌표 y좌표 \((-10,000,000 \leq, x, y \leq 10,000,000) x, y \in \mathbb{Z} \) 어떤 수 도시가 같은 점 위에 있는 경우는 없다. 테스트 케이스마다 가장 먼 두 점의 좌표를 출력한다. 2. 재정의 좌표평면에서 가장 먼 두 점의 위치를 구하시오 3. 해결 방법 Convex Hull Algorithm으로 볼록 껍질을 구한다. 임의의 두 점의 거리를 최장거리로 가정하자 두 벡터의 외적으로 캘리퍼..

나는 스위핑으로 풀었다. 분할 정복 풀이를 원하는 사람은 다른 블로그로 -> -> 1. 문제 2차원 평면 상에 n개의 점이 주어져 있을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오. \(n(2 \leq n \leq 100,000)\) \(\left|x \right|, \left|y \right| \leq 10000, x, y \in \mathbb{Z} \) 각 점의 x, y 좌표가 주어짐 가장 가까운 두 점의 거리의 제곱을 출력 2. 재정의 n개의 점들 중 가장 가까운 두 점 사이 거리 구하기 3. 해결 방법 Vertex.push_back({x, y}) 좌표들을 x축을 기준으로 오름차순 정렬하기 제일 왼쪽 부터 차례대로 점들을 확인하며 스위핑을 수행 set container에는 고..

#include #include #include #define LOOP(i, N) for(int i=1; i> N; LOOP(i, N) { int x, y; cin >> x >> y; p[i] = VEC(x, y); } } bool compare(const VEC &a, const VEC &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; } ll CCW(VEC &a, VEC &b, VEC &c) { return 1LL*(a.x*b.y + b.x*c.y + c.x*a.y - a.x*c.y - b.x*a.y - c.x*b.y); } int mai..

먼저 이를 이해하려면 행렬과 백터를 알고 있어야 되는데.... https://jordano-jackson.tistory.com/27 [Algorithm] 선분교차(Line-segment intersection) 판정 알고리즘 • Line-segment intersection 판별 알고리즘의 필요성 Line-segment의 교차 판정은 PS에서 흔히 다뤄지는 문제이다. 예컨대 네 점 이 주어졌다고 하자. 이 때 다음과 같은 두 선분을 생각할 수 있다. 이때 두 jordano-jackson.tistory.com 여기에 알고리즘이 자세히 적혀있다. 많은 조건 분기라는 알고리즘이 있어서 찾아봤는데 아무것도 안나와서 뭐지 했는데 풀어보면서 알았다. 선분의 케이스가 많아서 모두다 고려해야 됬던 거다. 케이스를 다 ..

#include #define LOOP(i, N) for(int i=0; i> N; LOOP(i, N) cin >> loc[i][0] >> loc[i][1]; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); input(); LOOP(i, N) { double x1=loc[i][0], y1=loc[i][1]; double x2=loc[(i+1)%N][0], y2=loc[(i+1)%N][1]; sum+=x1*y2-x2*y1; } cout