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/