Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:可能有几个炮弹落到同一个国家, 不要算重复了.

Posted by seabadases at 2004-09-14 20:40:10 on Problem 1264
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator