Poj Solution 1133

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;
}