1133.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

//精度；
//find(); 二分查找可以改进

#include"iostream.h"
#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;
}