AOJ 0269 - EastWind

問題 : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0269

平面幾何の参考にしたサイト : http://www.deqnotes.net/acmicpc/2d_geometry/

解法 :

点とそれぞれの扇型とを全て判定する。
扇型と点との判定
[1] : 点が半径内にあるかどうか
[2] : 扇内に点があるかどうか
扇の境界の二本のベクトル(v1,v2)と扇の中心から点へのベクトル(vとする)との外積を用いて判定する
(w+d/2)度のベクトルをv1,(w-d/2)とのベクトルをv2,外積の関数をcrossとすると
cross(v1,v)がCW(ClockWise|外積の符号が-)且つcross(v2,v)がCCW(CounterClockWise|外積の符号が+)

上記の[1][2]を満たせばその点は扇内にある

#include<iostream>
#include<vector>
#include<math.h>
#include<complex>

#define EPS 1e-4

#define PI 3.141592
#define EQ(a,b) (abs((a)-(b))<EPS)
using namespace std;

typedef complex<double> P;

vector<P> house;
vector<P> ume,sak,mo;

double cross(P v1,P v2){
	return v1.real()*v2.imag()-v1.imag()*v2.real();
}

bool che(P h,P t,double d,double w,double a){
	P v=h-t;
	if(!(abs(v)<a))return false;
	
	P v1=P(a*cos((w+d/2)/180*PI),a*sin((w+d/2)/180*PI));
	P v2=P(a*cos((w-d/2)/180*PI),a*sin((w-d/2)/180*PI));
	
	if(cross(v1,v)<0 && cross(v2,v)>0)return true;
	else return false;
}

int main(){
	int h,r;
	
	while(cin>>h>>r && h&&r){
		house.clear();
		ume.push_back(P(0,0));
		for(int i=0;i<h;i++){
			int x,y;
			cin>>x>>y;
			house.push_back(P(x,y));
		}
		
		int U,M,S,du,dm,ds;
		cin>>U>>M>>S>>du>>dm>>ds;
		for(int i=0;i<U;i++){
			int x,y;
			cin>>x>>y;
			ume.push_back(P(x,y));
		}
		for(int i=0;i<M;i++){
			int x,y;
			cin>>x>>y;
			mo.push_back(P(x,y));
		}
		for(int i=0;i<S;i++){
			int x,y;
			cin>>x>>y;
			sak.push_back(P(x,y));
		}
		
		
		int data[120];
		for(int i=0;i<120;i++)data[i]=0;
		for(int z=0;z<r;z++){
			int w,a;
			cin>>w>>a;
			
			for(int i=0;i<house.size();i++){
				bool ok=false;
				if(che(house[i],ume[0],du,w,a))ok=true;
				else continue;
				for(int j=1;j<=U;j++){
					if(che(house[i],ume[j],du,w,a))ok=false;
				}
				for(int j=0;j<M;j++){
					if(che(house[i],mo[j],dm,w,a))ok=false;
				}
				for(int j=0;j<S;j++){
					if(che(house[i],sak[j],ds,w,a))ok=false;
				}
				
				if(ok)data[i]++;
			}
		}
		
			int ans=0;
			int tmp=-1;
			for(int i=0;i<h;i++){
				if(ans<=data[i]){
					ans=data[i];
					tmp=i;
				}
			}
			if (ans==0)cout<<"NA"<<endl;
			else {
				for(int i=0;i<h;i++){
					if(i==tmp)cout<<i+1;
					else if(data[i]==ans)cout<<i+1<<" ";
					
				}
				cout<<endl;
			}
			
		
	}
}