목록기하학 (6)
넘치게 채우기
https://www.acmicpc.net/problem/22238BOJ - 가희와 btd5문제 유형: 수학, 기하학, 정렬, 구현, 시뮬레이션문제 난이도: Gold IV시간 제한: 1초메모리 제한: 512MB 문제btd5에는 Darting Gun Tower가 있습니다. Darting Gun Tower는 아래의 알고리즘으로 풍선을 공격합니다.공격하고자 하는 목표물의 방향으로 공격 방향을 바꿉니다.공격 방향에 있는 풍선들의 체력을 d씩 낮춥니다.Darting Gun Tower는 좌표 (0, 0)에 하나 있습니다.Darting Gun Tower가 공격을 하게 되면, 공격하는 방향에 놓인 모든 풍선들은 동일한 수치의 피해를 입히게 됩니다.초기에 풍선은 N개 있고, Darting Gun Tower는 공격을 M번..

https://codeforces.com/contest/2063/problem/DCodeforces Round 1000(Div. 2) - D. Game With Triangles문제 유형: 그리디, 수학, 기하학, 삼분 탐색, 구현, 투 포인터, 브루트 포스, 부분합, 구간합시간 제한: 2초메모리 제한: 256MB 문제There are n+m">n+m distinct points (a1,0),(a2,0),…,(an,0),(b1,2),(b2,2),…,(bm,2)">(a1,0),(a2,0),…,(an,0),(b1,2),(b2,2),…,(bm,2) on the plane. Initially, your score is 0">0. To increase your score, you can ..

https://www.acmicpc.net/problem/17387BOJ - 선분 교차 2문제 유형: 선형대수, 수학, 기하학문제 난이도: Gold II시간 제한: 0.25초메모리 제한: 512MB 문제2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다. 입력첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 출력L1과 L2가 교차하면 1, 아니면 0을 출력한다. 풀이처음에는 직선의 방정식을 이용해서..
https://www.acmicpc.net/problem/2166BOJ - 다각형의 면적문제 유형: 수학, 선형대수, 기하학문제 난이도: Gold V시간 제한: 2초메모리 제한: 128MB 문제2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. 출력첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다. 풀이볼록 또는 오목다각형에서 순서대로 N개의 점의 좌표가 주어진다면, 신발끈 공식을 이용해서 다각형의..
https://www.acmicpc.net/problem/1198BOJ - 삼각형으로 자르기문제 유형: 기하학, 브루트 포스문제 난이도: Silver II시간 제한: 2초메모리 제한: 128MB 문제볼록 다각형이 있고, 여기서 3개의 연속된 점을 선택해서 삼각형을 만든다. 그 다음, 만든 삼각형을 다각형에서 제외한다. 원래 다각형이 N개의 점이 있었다면, 이제 N-1개의 점으로 구성된 볼록 다각형이 된다. 위의 과정은 남은 다각형이 삼각형이 될 때까지 반복한다.볼록 다각형의 점이 시계 방향순으로 주어진다. 마지막에 남은 삼각형은 여러 가지가 있을 수 있다. 이때, 가능한 넓이의 최댓값을 구하는 프로그램을 작성하시오. 입력첫째 줄에 볼록 다각형 점의 수 N (3 ≤ N ≤ 35)이 주어진다. 둘째 줄부터 ..
https://www.acmicpc.net/problem/2403BOJ - 게시판 구멍 가리기문제 유형: 기하학, 수학, 이진 탐색문제 난이도: Gold III시간 제한: 2초메모리 제한: 128MB 문제교실 게시판에 압정을 사용하여 만들어진 구멍들을 안보이게 하기 위해서 두 개의 같은 크기의 정사각형 모양의 종이로 가리려고 한다. 두 종이는 서로 떨어져도 되고 서로 겹치는 부분이 있어도 상관없지만 모든 구멍들을 포함해야 한다. 단, 각 구멍은 크기가 매우 작아, x, y 좌표로 표현되는 점으로 표현되고, 구멍이 종이의 경계나 모서리에 놓이는 것도 종이에 포함되는 것으로 한다. 게시판에 각 구멍의 위치가 주어지고, 두 종이가 모두 게시판의 틀에 대해서 수평과 수직으로 놓인다고 할 때, 모든 구멍을..