ccw

외적을 이용해서 두 벡터의 상대적 위치를 파악하는 알고리즘이다.

 

ccw의 특징.

 

대충 증명법을 어디서 보고 끄적인것이다. 아 그냥 그렇구나 하고 넘겨도 된다.

 

 

이것으로 기초문제 

https://www.acmicpc.net/problem/11758

11758번: CCW

를 풀어보자.

#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;
}

 

 

 

 

 

또한, 외적 공식을 사용하면 다각형의 면적을 구할 수 있다.

세점을 알때 세점으로 두벡터를 만들어서 외적하면 크기가 평행사변형 넓이이고, 나누기2하면 삼각형의 넓이를 구할 수 있다.

이 그림 처럼 P1P2P3 삼각형의 넓이 + P1P3P4 삼각형의 넓이 +....+ P1Pn-1Pn 삼각형의 넓이

를 구하면 다각형의 넓이를 알수 있지 않을까?

 

https://www.acmicpc.net/problem/2166

2166번: 다각형의 면적

를 풀어보자.

 

 

 

#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);
 
}