http://poj.org/problem?id=1133
#include<iostream>
#include"math.h"
#include<algorithm>
#include<vector>
using namespace std;
struct point
{long x,y;};
typedef point vect;
struct
{point p;
int bright;
}star[1001];
int sn,vn;
double v_sin,v_cos,bi;
vect vec[1001];
double len;
point pt[1001];
inline double jl(point &a,point &b)
{return sqrt(double(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline long cheng(point &a,point &b)
{return a.x*b.y-a.y*b.x;}
void jiao(vect &a,vect &b)
{double t=sqrt(double(a.x*a.x+a.y*a.y)*(b.x*b.x+b.y*b.y));
v_sin=cheng(a,b)/t;//sqrt(a.x*a.x+a.y*a.y)/sqrt(b.x*b.x+b.y*b.y);
v_cos=(a.x*b.x+a.y*b.y)/t;//sqrt(a.x*a.x+a.y*a.y)/sqrt(b.x*b.x+b.y*b.y);
}
void sacal(vect &a,vect &b)
{bi=sqrt(double(b.x*b.x+b.y*b.y)/(a.x*a.x+a.y*a.y));}
inline double newx(double x,double y)
{return v_cos*x-v_sin*y;}
inline double newy(double x,double y)
{return v_sin*x+v_cos*y;}
int find(point &p)
{int i;
for(i=0;i<sn;i++)if(star[i].p.x==p.x&&star[i].p.y==p.y)return i;
return -1;
}
vector<int> answer;
long bright;long num;long self;
void judge(int s1,int s2)
{point a=star[s1].p,b=star[s2].p;
point p=b;
double x=0,y=0;int temp[1001];long br=star[s1].bright+star[s2].bright,at,bt;
vect v={b.x-a.x,b.y-a.y};
jiao(vec[1],v);
sacal(vec[1],v);
int i,s;
for(i=2;i<vn;i++)
{x=bi*newx(vec[i].x,vec[i].y);y=bi*newy(vec[i].x,vec[i].y);
at=long(x*1.00001);bt=long(y*1.00001);
if(fabs(x-at)>0.000001)break;
if(fabs(y-bt)>0.000001)break;
p.x+=at;p.y+=bt;
if((s=find(p))>=0){temp[i]=s;br+=star[s].bright;}
else break;
}
if(i<vn)return;
num++;
if(br>=bright){bright=br;answer[0]=s1;answer[1]=s2;
for(i=2;i<vn;i++)answer[i]=temp[i];}
}
void doit()
{bright=-9999999;num=0;
for(int i=0;i<sn;i++)
for(int j=0;j<sn;j++)
if(i!=j) judge(i,j);
}
int cmp(int i,int j)
{return star[i].p.x<star[j].p.x||
(star[i].p.x==star[j].p.x&&star[i].p.y<star[j].p.y);}
int findself(point &p)
{int i;
for(i=0;i<vn;i++)if(pt[i].x==p.x&&pt[i].y==p.y)return i;
return -1;
}
void judgeself(int s1,int s2)
{point a=pt[s1],b=pt[s2];
point p=b;
double x,y;
vect v={b.x-a.x,b.y-a.y};
jiao(vec[1],v);
sacal(vec[1],v);
int i;
for(i=2;i<vn;i++)
{x=bi*newx(vec[i].x,vec[i].y);
if(fabs(x-floor(x))>0.0001)break;
y=bi*newy(vec[i].x,vec[i].y);
if(fabs(y-floor(y))>0.0001)break;
p.x+=long(x*1.00001);p.y+=long(y*1.00001);
if(findself(p)>=0){}
else break;
}
if(i<vn)return;
self++;
}
int main()
{int i,j,a,b,c_n=0,t;
int x,y;char name[1000];
while(1)
{cin>>sn;if(sn==0)break;
cout<<"Map #"<<++c_n<<endl;
for(i=0;i<sn;i++)
cin>>star[i].p.x>>star[i].p.y>>star[i].bright;
cin>>t;
while(t--)
{cin>>vn;answer.resize(vn);
cin>>name>>x>>y;
pt[0].x=x;pt[0].y=y;
vec[0].x=0;vec[0].y=0;
for(j=1;j<vn;j++)
{cin>>a>>b;pt[j].x=a;pt[j].y=b;
vec[j].x=a-x;vec[j].y=b-y;x=a;y=b;}
if(vn==1)num=sn;
else {doit();self=0;
for(i=0;i<vn;i++)
for(j=0;j<vn;j++)
if(i!=j)judgeself(i,j);
num/=self;}
cout<<endl<<name<<" occurs "<<num<<" time(s) in the map."<<endl;
if(num){cout<<"Brightest occurrence:";
if(vn==1){int q=0;
for(j=1;j<sn;j++)
if(star[j].bright>star[q].bright||
(star[j].bright==star[q].bright&&cmp(j,q)))
q=j;
cout<<" ("<<star[q].p.x<<","<<star[q].p.y<<")"<<endl;
}
else {sort(answer.begin(),answer.end(),cmp);
for(j=0;j<vn;j++)
cout<<" ("<<star[answer[j]].p.x<<","
<<star[answer[j]].p.y<<")";
cout<<endl;}
}
}
cout<<"-----"<<endl;
}
return 0;
}