首页 > ACM题库 > HDU-杭电 > HDU 3882-Strange Galaxy-计算几何-[解题报告]HOJ
2015
04-13

HDU 3882-Strange Galaxy-计算几何-[解题报告]HOJ

Strange Galaxy

问题描述 :

ACM space explorer discovered a special space in an observation. There are many strange stars in it, and we call them S-stars. Each three of them, such as A, B, C, can form an opaque triangle area ABC, and the area can absorb the light inside O-ABC for the point light source O which made O can only light the space except an infinite triangular file shaped space whose boundaries are ray OA, OB and OC.

In order to know the size of the area that a point light source O can light at a specific direction, we normally choose a plane P as reference, consider O’s invisible area in P. If the area size is infinite or 0, we consider the direction as a bad one. We take this direction as a reference only if the area size is finite and non-zero.

Then we’ll give you another set of normal stars, we’d like to know the percentage of those couldn’t be lighted among all the normal stars.

输入:

Multiple cases, no more than 100, test case ends with four zeros.
All numbers are integers, in each case:
Line 1: a, b, c and d, represent the reference plane: ax+by+cz=d;
Line 2: n (0<n<=100), number of S-stars
Line 3 �C n+2: x, y and z, coordinate of each S-star
Line n+3: x0, y0 and z0, coordinate of point light source O
Line n+4: m (0<m<100), number of normal stars
Line n+5 �C n+m+4: x, y and z, coordinate of each normal star

Notice: S-star and normal star may coincide. We guarantee that if there exist S-stars, they are not all at the same plane. The point light source is not on the reference plane and doesn’t coincide with other stars. The absolute value of each coordinate number is below 10000.

输出:

Multiple cases, no more than 100, test case ends with four zeros.
All numbers are integers, in each case:
Line 1: a, b, c and d, represent the reference plane: ax+by+cz=d;
Line 2: n (0<n<=100), number of S-stars
Line 3 �C n+2: x, y and z, coordinate of each S-star
Line n+3: x0, y0 and z0, coordinate of point light source O
Line n+4: m (0<m<100), number of normal stars
Line n+5 �C n+m+4: x, y and z, coordinate of each normal star

Notice: S-star and normal star may coincide. We guarantee that if there exist S-stars, they are not all at the same plane. The point light source is not on the reference plane and doesn’t coincide with other stars. The absolute value of each coordinate number is below 10000.

样例输入:

0 0 1 0
8
1 1 1
1 -1 1
-1 1 1
-1 -1 1
1 1 0
1 -1 0
-1 1 0
-1 -1 0
2 2 1
4
0 0 1
0 0 0
0 1 0
1 0 1
1 0 0 -2
8
1 1 1
1 1 -1
1 -1 1
1 -1 -1
-1 1 1
-1 1 -1
-1 -1 1
-1 -1 -1
2 0 0
10
1 0 0
2 0 0
-1 -1 1
1 1 -1
0 0 0
2 0 0
3 0 0
2 2 2
1 -1 -1
-1 1 -1
1 1 1 1
0
0 0 0
1
1 1 1
0 0 0 0

样例输出:

INF
40.00%
ZERO

哈我好像是HDU上惟一一个过了这题的人(可惜是用vjudge交的不是我自己的账号)……

题意很简单,就是说给定空间中很多点和一个参照点,对于空间中的其他点来说,如果这个点在这个参照点到给定的其中三个点的射线所组成的的无穷三棱锥里,那么这点就是没有被照射到,否则就是照射到了。现在给定一个参考平面,不过参照点,问这个平面上没有被照射到的点所组成区域的面积是否有限且不为零;如果是,再输出另给定的一些点中没有被照射到的点占的百分比。

这题表面上看很复杂,但是注意到,因为参考平面不过参照点,事实上不被照射的面积只与参照点到所有给定点的射线与该平面的交点个数t有关。如果t=n,则一定有限,如果t=0,则一定为零,其他情况就是无穷。而对于有限的情况,同样要考虑一个新给定点有没有被照射到,只要考虑参照点到它的射线是否与参考平面相交,以及交点是否在已给定点在这个平面上组成的凸包内部(不包括边界,这点可以直接从样例看出)。当然注意考虑参照点与给顶点重合的情况。虽然参考平面可能倾斜,但总可以把其上的点投影到三个坐标面,这样就可以用二维的凸包。具体看程序吧……

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;

const double eps=1e-9;
int dcmp(double x){if(x<-eps) return -1;return x>eps;}
struct point3
{
	double x,y,z;
	point3(double x=0,double y=0,double z=0):x(x),y(y),z(z){}
	void read(){int xt,yt,zt;scanf("%d %d %d",&xt,&yt,&zt);x=xt;y=yt;z=zt;}
};

point3 operator -(point3 a,point3 b){return point3(a.x-b.x,a.y-b.y,a.z-b.z);}
point3 operator *(point3 a,double b){return point3(a.x*b,a.y*b,a.z*b);}
bool operator <(point3 a,point3 b){return a.x<b.x||(dcmp(a.x-b.x)==0&&a.y<b.y)||(dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0&&a.z<b.z);}
bool operator ==(point3 a,point3 b){return !(a<b||b<a);}
double dot(point3 a,point3 b){return a.x*b.x+a.y*b.y+a.z*b.z;}
double cross(point3 a,point3 b){return a.x*b.y-a.y*b.x;}
double length(point3 a){return sqrt(dot(a,a));}

int convexhull(point3 *p,int n,point3 *ch)  
{  
	sort(p,p+n);
	int nt=0;
	for(int i=0;i<n;i++)
	{
		if(!nt||!(p[nt-1]==p[i])) p[nt++]=p[i];
	}
	n=nt;
	int m=0;  
	for(int i=0;i<n;i++)  
	{  
		while(m>1&&dcmp(cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0) --m;  
		ch[m++]=p[i];  
	} 
	int k=m;  
	for(int i=n-2;i>=0;i--)  
	{  
		while(m>k&&dcmp(cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0) --m;  
		ch[m++]=p[i];  
	}  
	if(n>1) --m;  
	return m;  
}  


int n,m;
double a,b,c,d;
point3 p[105],p0,q[105],ch[105];

int main()
{
	int i,j;
	int at,bt,ct,dt;
	while(scanf("%d %d %d %d",&at,&bt,&ct,&dt)!=EOF&&(at||bt||ct||dt))
	{
		a=at,b=bt,c=ct,d=dt;
		scanf("%d",&n);
		for(i=0;i<n;i++) p[i].read();
		p0.read();
		for(i=0;i<n;i++) p[i]=p[i]-p0;
		d=d-dot(point3(a,b,c),p0);
		scanf("%d",&m);
		for(i=0;i<m;i++) q[i].read(),q[i]=q[i]-p0;
		int nt=0;
		for(i=0;i<n;i++)
		{
			double te=dot(point3(a,b,c),p[i]);
			if(dcmp(te)==0) continue;
			if(dcmp(d/te)>0) p[i]=p[i]*(d/te),++nt;
		}
		if(nt==0) printf("ZERO\n");
		else if(nt<n) printf("INF\n");
		else
		{
			for(i=0;i<n;i++)
			{
				if(ct) p[i].z=0;
				else if(bt) swap(p[i].y,p[i].z),p[i].z=0;
				else swap(p[i].x,p[i].z),p[i].z=0;
			}
			nt=convexhull(p,n,ch);
			int rt=0;
			//for(i=0;i<nt;i++) cout<<ch[i].x<<" "<<ch[i].y<<endl;
			for(i=0;i<m;i++)
			{
				double te=dot(point3(a,b,c),q[i]);
				if(dcmp(te)==0||dcmp(d/te)<0) continue;
				q[i]=q[i]*(d/te);
				if(ct) q[i].z=0;
				else if(bt) swap(q[i].y,q[i].z),q[i].z=0;
				else swap(q[i].x,q[i].z),q[i].z=0;
				//cout<<q[i].x<<" "<<q[i].y<<endl;
				for(j=0;j<nt;j++)
				{
					if(dcmp(cross(q[i]-ch[j],ch[(j+1)%nt]-ch[j]))>=0) break;
				}
				if(j>=nt) {++rt;/*cout<<q[i].x<<" 1 "<<q[i].y<<endl;*/}
			}
			printf("%.2lf%%\n",100.0*rt/m);
		}
		
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/sysuyudx/article/details/41012971