너와 나의 스토리

문제: www.acmicpc.net/problem/11758 문제 풀이: 외적을 이용하자 이렇게 구해지는 cross product(외적) 값이 [양수 or 음수 or 0]인지에 따라 두 벡터의 상대적인 방향을 확인할 수 있다. 다음과 같이 시계 방향인 것을 CW, 반 시계 방향인 것을 CCW라고 한다. 외적 값이 음수인 경우 CW, 양수인 경우 CCW, 0인 경우 일직선(두 선분이 겹쳐서 일직선을 그림)임을 알 수 있다. 소스 코드: #include #include #include #include #include #include using namespace std; typedef pair P; vector points; int op(int a, int b){ return points[a].first*po..

문제: https://www.acmicpc.net/problem/3878 소스 코드: #include #include #include #include #include #include #include using namespace std; typedef long double ll; typedef pair P; int startpoint, tc, n, m; ll ax, ay; vector black, white; vector v1,v2; bool cmp(const P a, const P b) { if ((ax - b.first) * (ay - a.second) == (ax - a.first) * (ay - b.second)) { if (a.second == b.second) return a.first < b...

문제: https://www.acmicpc.net/problem/6439 문제 풀이: 직사각형의 대각선 두 점으로 (a,b), (c,d)를 입력 받았을 때, 나머지 두 점은 (c,b), (a,d)가 된다. 변 4개와 직선의 ccw를 구해 교차하는지 확인하고 한 변이라도 교차하면 T를 출력하고, 다른 변은 더 이상 보지 않아도 된다. 주의! 선분이 직사각형의 내부에 존재할 수도 있다. 확인을 위해 직사격형과 선분에서 최소/최대 x값과 최소/최대 y값을 구하고 비교해준다. 소스코드: ...더보기 typedef long long ll; typedef pair P; ll tc, a, b, c, d,ix1,iy1,ix2,iy2; ll ccw(P, P, P); bool func(P p1, P p2, P p3,P p..

문제: https://www.acmicpc.net/problem/1708 문제 풀이: Convex Hull 알고리즘 중 Graham's Scan 방법을 이용하여 풀었다. (다른 방법으로는 monotone chain convex hull 방법이 있다) 입력 받은 좌표 중 가장 작은 y값을 가진 점 중 가장 작은 x값을 가진 점을 기준점으로 삼는다. 그 기준점과 모든 점과의 기울기를 기준으로 좌표를 정렬한다. 기울기가 작은 점들부터 비교 연산을 시작한다. 처음에 벡터(나는 벡터를 스택처럼 사용)에 기준점과 기울기가 가장 작은 점, 두 점을 백터에 넣는다. 그 후 인덱스(idx)를 증가시켜가며 현재 벡터의 top에 있는 2점을 기준으로 ccw가 양수이면 해당 좌표의 인덱스를 벡터에 넣고 idx++ ccw가 음..

문제: https://www.acmicpc.net/problem/2162 문제 풀이: 두 선분을 뽑아 만나는지 확인한다 선분1에서 선분2의 한 점과의 ccw, 다른 점과의 ccw가 둘 다 0이고 반대의 경우도 다 0이면 두 선분이 일직선 상에 존재한다는 말이므로 따로 if문을 만들어서 겹치는지 확인해준다 다 0이 아니라면 선분1에서 선분2로의 ccw곱이 음수이고, 선분2에서 선분1로의 ccw곱도 음수이면 둘은 겹친다고 볼 수 있다. 겹친다면 union find 알고리즘을 이용해서 연결 시켜준다. 각 그룹에 속하는 선분의 개수를 알기 위해 루트에 새로운 선분 그룹을 연결할 때, 그 인원수를 루트 부모 변수에 더해준다. 즉, 부모를 기록하는 변수인 p를 처음에 -1로 초기화하고 다른 선분이 추가되면 -2, ..

문제: https://acmicpc.net/problem/2166 문제 풀이: 한 점을 잡고 두 점씩 뽑아 (ccw 값/2)를 해준다. * ccw 값: 두 변을 기준으로한 평행사변형의 넓이 빨간 원이 기준 소스 코드: typedef pair P; vector v; long double res; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; while (n--) { long double x, y; cin >> x >> y; v.push_back({ x,y }); } long double ax = v[0].first; long double ay = v[0].second; for (int i = ..