백준/기하5 백준 2166 c++ -[PlusUltraCode] [필자사고] 고등학교 때 배운 신발끈 공식을 적용하면 쉽게 풀 수 있는 문제이다 x1 x2 x3 x1 y1 y2 y3 y1 (x1*y2+x2*y3+x3*y1)-(x2*y1+x3*y2+x1*y3)= ccw 문제에서 다각형의 넓이를 구해야 되므로 x3,y3을 원점이라 하고 각 선분마다 ccw값을 구하고 결과값에 더해준다. 마지막으로 절대값을 취해주고 2로 나눠주면 답이 나온다. #include #include #include #include using namespace std; int N; long x[10001]; long y[10001]; //x1 x2 0 x1 //y1 y2 0 y1 //x1*y2 -x2*y1; void Input() { cin >> N; for (int i = 0; i < N; i++.. 2024. 2. 19. 백준 2162 c++ - [PlusUltraCode] [필자 사고] 백준 17387번으로 선분의 교차여부를 코드로 작성하였다. 이 문제는 그에 더해서 Union 알고리즘을 사용하여 문제를 해결할 수 있는지 묻는 문제였다. 먼저 선분의 교차여부 알고리즘을 만들고 Union 알고리즘을 아용하여 그룹의 최대 갯수를 구했다. #include #include #include #include using namespace std; typedef struct Point { long x1, y1, x2, y2; }Point; vector parent; vector visited; vector groupCount; int find(int a) { if (a == parent[a])return a; else return parent[a] = find(parent[a]); } .. 2024. 2. 19. 백준 17387 c++ -선분 교차2 [PlusUltraCode] [필자 생각 ] 문제를 보고 CCW 알고리즘을 이용해야 된다는 생각이 들었다. CCW알고리즘 공식은 알고 있었지만 어떻게 이용해서 선분이 교차되는지 판단하는데는 문제가 있었다. 고등학교 때 배운 선분 교차 방법을 생각해 봤지만 코드로 짜기에는 무척 복잡해졌다. 몇몇 자료를 찾아보니 다음과 같은 해결책을 찾았다. [해결] 1. 두 선분이 방향과는 상관없이 일단 겹쳐져 있나? 2. 두 선분이 겹쳐진거 상관없이 CCW를 이용하여 일직선이냐 아니냐? 이 두가지 함수를 구하면 된다. [소스코드] #include #include #include using namespace std; int CCW(long x1, long y1, long x2, long y2, long x3, long y3) { //x1 x2 x3 .. 2024. 2. 16. 백준 11758 c++ -PlusUltraCode CCW알고리즘을 알고 있으면 쉽게 풀수 있는 문제이다. /* x1 x2 x3 x1*/ /* y1 y2 y3 y1*/ CCW알고리즘은 이런식으로 대각선끼리 곱해주고 빼주면 된다. [소스코드] #include #include #include #include #include #include using namespace std; int main(void) { int x1, x2, x3, y1, y2, y3; /* x1 x2 x3 x1*/ /* y1 y2 y3 y1*/ cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3; int CCW = ( (x1 * y2) + (x2 * y3) + (x3 * y1) ) - ((x2* y1) + (x3 * y2) + (x1 * y3)); if (CCW > 0.. 2024. 2. 15. 이전 1 2 다음