백준 13352, 석양이 진다...
개요 문제 링크 플래 4, Geometry, Randomization 두 개 이하의 직선으로 모든 점을 포함할 수 있는지 여부를 구하기 접근 10523을 풀고 너무 신기해서 풀어본 다음 문제, 로직은 똑같으니 궁금하면 10523 글을 읽어보길 바란다. 마찬가지로 입력 최적화를 하고, long long을 사용하고, CCW가 0인 점의 개수를 세고, 랜덤 추출을 하는데, 이번에는 20번만 해주면 된다. 왜 랜덤 추출 횟수가 줄어들었을까? 이전보다 추출의 필요성이 줄어들었기 때문인데, 10523에서는 직선에 포함된 점의 개수를 구하는 것이므로 서로 다른 직선을 최대한 많이 구해봐야 한다. 이 문제는 한 직선을 잡고, 그 직선과 다른 직선을 잡기만 하면 된다. 만약 다른직선이 잡히기만 했다면, 전체 점이 포함되..
2023. 3. 11.
백준 1077, 넓이
개요 문제 링크 플래 1, Geometry, 컨벡스 헐 두 볼록다각형의 겹치는 넓이 구하기 접근 구현량이 많았던 까다로운 문제, 생각할 부분이 많아서 간략화를 했음에도 코드가 3000비트 정도 된다. 전부 구조체로 구현했는데, 구현할 구조체는 점, 선, 다각형이다. 생각 자체는 구현할 수만 있다면 크게 복잡하지 않다. 만약 서로 포함하는 관계라면, 볼록껍질의 넓이가 두 다각형의 넓이 중 하나와 같을 것이다. 두 다각형을 P,Q라고 할 때 P와 같으면 Q의 넓이가, Q와 같으면 P의 넓이가 정답이 될 것이다. 나머지는 겹치는 다각형을 어떻게든 구해내서 출력하면 된다. 만약 겹치지 않으면? 다각형의 점의 개수가 0개일테니 알아서 넓이를 구하는 과정에서 0이 출력된다. 겹치는 다각형은 어떻게 구해주냐? 보통은..
2023. 2. 28.
백준 20149, 선분 교차 3
개요 문제 링크 플래 4, Geometry 교차하는 선분의 교차점, 혹은 선분의 포함 여부 출력 접근 난데없이 날아온 재채점과 WA 때문에 다시 풀었다. 문제점은 끝점에서 만날 때 양 점 중 출력해야 하는 점을 잘못 선택한 것이었다. 날벼락 맞은 느낌에 숏코딩으로 복수했다. 선분이 교차하는 경우의 수는 몇 가지일까? 1) 크로스한다. 2) 평행하며 겹친다. 3) 평행하며 만나지 않는다. 4) 평행하며 끝점에서 만난다. 5) 평행하지 않고 만나지 않는다. 와 같은 경우가 있다. 각각을 그림으로 나타내면 이렇게 되겠다. 3. 먼저 ccw를 알고 있다는 가정 하에 설명을 해보자면, 일반적인 선분의 교차여부는 이렇다. ccw(a,b,c) != ccw(a,b,d) && ccw(a,c,d) != ccw(b,c,d)..
2023. 2. 13.
백준 1151, 그림자
개요 문제 링크 플래 4, 기하학 3차원 도형의 그림자의 넓이 접근 많은 조건 분기라고 되어있는데 조건이 생각보다 많지 않았음. 선인 경우는 두 좌표 이상이 같으면 되고, 무한인 경우는 z좌표가 하나라도 크면 된다. 나머지는 정사영 좌표를 구해서 넓이를 구하면 되는데, 넓이 구할 방법이 생각나지 않아서 그냥 convex hull로 갔다. 어차피 점의 개수는 최대 8개니까 시간은 맘대로 써도 됨. 정사영 구하는 방법은 기하와 벡터에서 공부했던 직선의 방정식을 응용하면 된다. (x-a)/(p-a) = (y-b)/(q-b) = (z-c)/(r-c) z = 0 x = a-(p-a)*c/(r-c), y = b-(q-b)*c/(r-c) Pseudo code proj(point {a,b,c}, point {p,q,r..
2023. 2. 8.
