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