寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C++ #CGL_3_C : Polygon-Point Containment

Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。

・問題 "Polygon-Point Containment"
https://onlinejudge.u-aizu.ac.jp/problems/CGL_3_C
・多角形-点の包含

僕が作成、提出したコードは、以下のとおりです。

Aizu Online Judge in C++ #CGL_3_C : Polygon-Point Containment
/*
Aizu Online Judge in C++ #CGL_3_C : Polygon-Point Containment
https://onlinejudge.u-aizu.ac.jp/problems/CGL_3_C
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> point;
vector<point> pol;
bool eq(double a,double b){
    return (abs(a-b)<=(1e-9));
}
bool on_segment(point a,point b,point c){
    return eq(abs(b-a),abs(a-c)+abs(b-c));
}
double get_r(point a,point b,point c){
    b-=a;
    c-=a;
    b*=conj(c);
    return arg(b);
}
int f(point a){
    for(int i=0;i<pol.size();i++){
        if(on_segment(pol[i],pol[(i+1)%pol.size()],a)){
            return 1;
        }
    }
    double sum=0;
    for(int i=0;i<pol.size();i++){
        sum+=get_r(a,pol[i],pol[(i+1)%pol.size()]);
    }
    if(eq(sum,0)){
        return 0;
    }
    return 2;
}
int main(void){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        double a,b;
        cin>>a>>b;
        pol.push_back(point(a,b));
    }
    int q;
    cin>>q;
    while(q--){
        double a,b;
        cin>>a>>b;
        cout<<f(point(a,b))<<endl;
    }
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/