Algoogle

Algorithm for Programming Contest

AOJ 0012 A Point in a Triangle

Category: AOJ Tag: geometry

A Point in a Triangle

問題概要


解法


多角形と点の包含関係をやればいい

コード


(0012.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
typedef complex<double> P;
typedef vector<P> G;
inline double dot(const P& a, const P& b) { return real(conj(a)*b);}
inline double cross(const P& a, const P& b) { return imag(conj(a)*b);}

#define curr(g, i) g[i]
#define next(g, i) g[(i+1)%g.size()]
enum { OUT, ON, IN };
int contains(const G& g, const P& p) {
    bool in = false;
    for (int i = 0; i < g.size(); ++i) {
        P a = curr(g,i) - p, b = next(g,i) - p;
        if (imag(a) > imag(b)) swap(a, b);
        if (imag(a) <= 0 && 0 < imag(b))
            if (cross(a, b) < 0) in = !in;
        if (cross(a, b) == 0 && dot(a, b) <= 0) return ON;
    }
    return in ? IN : OUT;
}

int main(){
    G g(3);
    P p;
    while(~scanf("%lf %lf %lf %lf %lf %lf %lf %lf",
                 &g[0].real(), &g[0].imag(), &g[1].real(), &g[1].imag(), &g[2].real(), &g[2].imag(),
                 &p.real(), &p.imag())){
        cout << (contains(g,p)==IN? "YES": "NO") << endl;
    }
}

Comments