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