| ||||||||||
| 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 | |||||||||
实在是搞不懂了.麻烦大虾看下,太弱了.wa几十次了.#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator