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

实在是搞不懂了.麻烦大虾看下,太弱了.wa几十次了.

Posted by xiaohuang at 2005-08-22 20:03:40 on Problem 1375
#include<stdio.h>
#include<cmath>
#define N 501
#define T rigion
typedef struct{
double x,y,r;
}Circle;
typedef struct{
double left,right;
}rigion;
bool tag[N];
rigion R[N],r[N];
Circle cir[N];
double bx,by;
int n,u=0;

void Count_rigion(){
	int i;
	double d,cta,l;
	double k,k1,k2;
	for(i=1;i<=n;i++)
	{
		d=sqrt((bx-cir[i].x)*(bx-cir[i].x)+(by-cir[i].y)*(by-cir[i].y));
		cta=asin(cir[i].r/d);
		if(cir[i].x==bx)//圆心坐标与光源坐标相同//
		{
			l=by*tan(cta);
			R[i].left=bx-l,R[i].right=bx+l;
		}
		else if(cir[i].x+cir[i].r==bx){
		l=by*tan(2*cta);
		R[i].left=bx-l;
		R[i].right=bx;
		}
		else if(cir[i].x-cir[i].r==bx){
		l=by*tan(2*cta);
		R[i].left=bx;
		R[i].right=bx+l;
		}
		else{
			k=(by-cir[i].y)/(bx-cir[i].x);
			k1=(k-tan(cta))/(1+k*tan(cta));
			k2=(k+tan(cta))/(1-k*tan(cta));
			R[i].left=bx-by/k1;
			R[i].right=bx-by/k2;
		}        
	}

}
int Partition(T a[],int low,int high){
   R[0]=R[low];
   double pivotkey=R[low].left;
   while(low<high){
	   while(low<high&&R[high].left>=pivotkey) --high;
	   R[low]=R[high];
	   while(low<high&&R[high].left<=pivotkey) ++low;
	   R[high]=R[low];
   }
   R[low]=R[0];
   return low;
}
void QSort(T a[],int low,int high){
  int pivotloc;
  if(low<high){
	  pivotloc=Partition(a,low,high);
	  QSort(a,low,pivotloc-1);
	  QSort(a,pivotloc+1,high);
  }
}
void QuickSort(T a[],int n){
QSort(a,1,n);
}
int check(){
int i;
for(i=1;i<=n;i++)
if(tag[i]==0) return i;
return 0;
}
void fun()
{
   int i,m;
   double start=0,end=0;
    m=1;
   while(1){ 
	  m=check();
	  if(m==0)
		  break;
	   start=R[m].left,end=R[m].right;
	   tag[m]=1;	   	  
	    for(i=m+1;i<=n;i++)
			         if(R[i].left>end) 
					 {
				         r[u].left=start;
                         r[u].right=end;
	                     u++;	
				        break;
					 }
			else {
				if(R[i].right>end) 			
					end=R[i].right;
				tag[i]=1;
			}
                                 
		
   }
   r[u].left=start;
   r[u].right=end;
}

int main()
{
	int i,j;
	while(scanf("%d",&n)!=EOF&&n)
	{
       scanf("%lf %lf",&bx,&by);
	   for(i=1;i<=n;i++)	   
	   {
		   scanf("%lf %lf %lf",&cir[i].x,&cir[i].y,&cir[i].r);
	   tag[i]=0;
	   }
	    u=0;
	    Count_rigion();
        QuickSort(R,n);
		fun();
		for(j=0;j<=u;j++)
		{
			if(r[j].left<0)
				r[j].left-=0.005;
			if(r[j].right<0)
				r[j].right-=0.005;
			printf("%.2lf %.2lf\n",r[j].left,r[j].right);
		}		
		printf("\n");
	}

return 0;	
}

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