| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:可能有几个炮弹落到同一个国家, 不要算重复了.In Reply To:Re:可能有几个炮弹落到同一个国家, 不要算重复了. Posted by:seabadases at 2004-09-14 20:39:30 #include<vector> #include<iostream> #include<cstdio> #include<cmath> using namespace std; int n,m; int x[200],y[200]; vector<int> stackx,stacky; vector<int> vx[21],vy[21]; double area[21]; void swap(int &a,int &b) { int t=a;a=b;b=t; } int Multi(int x1,int y1,int x2,int y2,int x0,int y0) { int Mul=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0); return Mul; } bool Comp(int x1,int y1,int x2,int y2) { int t=Multi(x1,y1,x2,y2,x[0],y[0]); if((t>0)||((t==0)&&(x1-x[0])*(x1-x[0])+(y1-y[0])*(y1-y[0]) <(x2-x[0])*(x2-x[0])+(y2-y[0])*(y2-y[0]))) return true; return false; } void Qsort(int m,int n) { int i,j,s; if(m>=n)return; i=m; j=n+1; s=m; while(i<j) { i++; while (Comp(x[i],y[i],x[m],y[m]))i++; j--; while (Comp(x[m],y[m],x[j],y[j]))j--; if(i<j) swap(x[i],x[j]),swap(y[i],y[j]); } swap(x[m],x[j]),swap(y[m],y[j]); Qsort(m,j-1); Qsort(j+1,n); } void Graham() { Qsort(0,n-1); stackx.push_back(x[0]); stackx.push_back(x[1]); stackx.push_back(x[2]); stacky.push_back(y[0]); stacky.push_back(y[1]); stacky.push_back(y[2]); for(int i=3;i<n;i++) { while(Multi(x[i],y[i],stackx[stackx.size()-1],stacky[stacky.size()-1], stackx[stackx.size()-2],stacky[stacky.size()-2])>=0) stackx.pop_back(),stacky.pop_back(); stackx.push_back(x[i]),stacky.push_back(y[i]); } } double s(vector<int> vx,vector<int>vy) { vx.push_back(vx[0]); vy.push_back(vy[0]); double area=0; for(int i=1;i<vx.size();i++) area+=double(vx[i-1]*vy[i]-vx[i]*vy[i-1]); area/=2; return area; } double tri_area(int x1,int y1,int x2,int y2,int x3,int y3) { double area=0; area+=x1*y2-x2*y1; area+=x2*y3-x3*y2; area+=x3*y1-x1*y3; area/=2; if(area<0)area=-area; return area; } bool in_it(int x,int y,vector<int> vx,vector<int> vy,int N) { vx.push_back(vx[0]); vy.push_back(vy[0]); double S=0; for(int i=0;i<vx.size()-1;i++) { double temp=tri_area(x,y,vx[i],vy[i],vx[i+1],vy[i+1]); S+=temp; } if(fabs(S-area[N])<0.0001)return true; return false; } int main() { int i,num[21],kindom=0,N; while(cin>>N&&N>0) { kindom++; num[kindom]=N; for(i=0;i<num[kindom];i++) { cin>>x[i]>>y[i]; } stackx.clear(); stacky.clear(); n=num[kindom]; Graham(); vx[kindom]=stackx; vy[kindom]=stacky; } for(i=1;i<=kindom;i++) { area[i]=s(vx[i],vy[i]); if(area[i]<0)while(1){}; } int tx,ty; int able[21]; for(i=1;i<=kindom;i++) able[i]=0; while(cin>>tx>>ty) { for(i=1;i<=kindom;i++) if(in_it(tx,ty,vx[i],vy[i],i)) able[i]=1; } double total=0; for(i=1;i<=kindom;i++) total+=able[i]*area[i]; printf("%.2lf\n",total); } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator