알고리즘 기술
ccw
헐랭미
2020. 7. 16. 13:37
외적을 이용해서 두 벡터의 상대적 위치를 파악하는 알고리즘이다.
이것으로 기초문제
https://www.acmicpc.net/problem/11758
11758번: CCW
첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.
www.acmicpc.net
를 풀어보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int x1, y1, x2, y2, x3, y3;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
int su = x1 * y2 + x2 * y3 + x3 * y1 - x2 * y1 - x3 * y2 - x1 * y3;
if (su > 0)
cout << 1;
else if (su == 0)
cout << 0;
else
cout << -1;
}
|
cs |
또한, 외적 공식을 사용하면 다각형의 면적을 구할 수 있다.
세점을 알때 세점으로 두벡터를 만들어서 외적하면 크기가 평행사변형 넓이이고, 나누기2하면 삼각형의 넓이를 구할 수 있다.
이 그림 처럼 P1P2P3 삼각형의 넓이 + P1P3P4 삼각형의 넓이 +....+ P1Pn-1Pn 삼각형의 넓이
를 구하면 다각형의 넓이를 알수 있지 않을까?
https://www.acmicpc.net/problem/2166
2166번: 다각형의 면적
첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다.
www.acmicpc.net
를 풀어보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <iostream>
#include <cmath>
#define ld long double
using namespace std;
class Point
{
public :
ld x, y;
};
ld get(Point p1, Point p2, Point p3)
{
return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y -
(p1.y * p2.x + p2.y * p3.x + p3.y * p1.x);
}
int main()
{
int n;
cin >> n;
Point p[10000];
for (int i = 0; i < n; i++)
cin >> p[i].x >> p[i].y;
Point base = p[0];
ld ans = 0;
for (int i = 2; i < n; i++)
{
ans += get(p[0], p[i - 1], p[i]);
}
double ans2 = fabs(ans) / 2;
cout << fixed;
cout.precision(1);
cout << ans2;
cout.unsetf(ios::fixed);
}
|
cs |