首页 > 代码库 > UVALive 6092 Catching Shade in Flatland --枚举+几何计算
UVALive 6092 Catching Shade in Flatland --枚举+几何计算
题意：x=[-200,200],y=[-200,200]的平面，一天中太阳从不同角度射到长椅（原点(0,0)）上，有一些树（用圆表示），问哪个时刻（分钟为单位）太阳光线与这些圆所交的弦长总和最长。太阳距离原点总是500m。(这些圆不会互相相交，每个圆都不包括原点或者不经过原点）
解法：直接暴力24*60分钟，找出此时的角度，然后求出直线方程，再枚举每个圆，求出弦长。注意这里每个圆都不包括原点，所以直线与圆的交点一定在同一侧，所以。。我当时想多了，没看清题目。把他当成可以包含原点了，代码超长，幸好过了。
代码：
没想多应该这样就可以了：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <cstdlib>#define INint 2147483647#define pi acos(-1.0)#define eps 1e-4using namespace std;#define N 100102#define M 22typedef struct point{ double x,y; point(double x=0,double y=0):x(x),y(y){}}Vector;double DegtoRad(double deg){ return deg/180.0*pi;}int dcmp(double x){ if(fabs(x)<eps) return 0; return x<0?-1:1;}Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}Vector operator - (point A,point B){return Vector(A.x-B.x,A.y-B.y); }Vector operator * (Vector A,double p){return Vector(A.x*p,A.y*p);}Vector operator / (Vector A,double p){return Vector(A.x/p,A.y/p);}bool operator == (const point& a,const point& b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}bool operator < (const point& a,const point& b){return a.x<b.x ||(a.x==b.x&&a.y<b.y);}double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;} //叉积 ，大于零说明B在A的左边。小于零说明B在A的右边double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;} //点积double length(Vector A){return sqrt(Dot(A,A));} //向量长度double DistanceToSegment(point P,point A,point B){ if(A==B) return length(P-A); Vector v1=B-A,v2=P-A,v3=P-B; if(dcmp(Dot(v1,v2))<0) return length(v2); else if(dcmp(Dot(v1,v3))>0) return length(v3); else return fabs(Cross(v1,v2))/length(v1);}point p[205];double ra[205];int main(){ int n,i,j; while(scanf("%d",&n)!=EOF && n) { for(i=0;i<n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&ra[i]); double maxi = 0.0; int S = 24*60; for(i=0;i<S;i++) { point A,B,C; A = point(0.0,0.0); double rad = DegtoRad(i/4.0); B = point(500*sin(rad),500*cos(rad)); double sum = 0.0; for(j=0;j<n;j++) { C = p[j]; double dis = DistanceToSegment(C,A,B); if(dis >= ra[j]) continue; sum += 2.0*sqrt(ra[j]*ra[j]-dis*dis); } maxi = max(maxi,sum); } printf("%.3lf\n",maxi); } return 0;}
当时的代码（考虑了可能包含原点）：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <cstdlib>#define pi acos(-1.0)using namespace std;#define N 100102#define M 22struct node{ double x,y,r;}p[205];int getPlane(double nx,double ny){ if(nx > 0 && ny > 0) return 1; else if(nx > 0 && ny < 0) return 2; else if(nx < 0 && ny < 0) return 3; else if(nx < 0 && ny > 0) return 4; else return 1;}double dis(int nx,int ny){ return sqrt(nx*nx + ny*ny);}int main(){ int n,i,j; while(scanf("%d",&n)!=EOF && n) { for(i=0;i<n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r); int S = 24*60; double Si = 24.0*60.0; int Plane; double maxi = 0.0; for(i=0;i<S;i++) { if(i == 0 || i == 360 || i == 720 || i == 1080) continue; double A = tan(2*pi*(double)i/Si); double B = -1.0; double k = A; double di = sqrt(A*A+B*B); if(i > 0 && i < 360) Plane = 1; else if(i > 360 && i < 720) Plane = 2; else if(i > 720 && i < 1080) Plane = 3; else Plane = 4; double sum = 0.0; for(j=0;j<n;j++) { double x = p[j].x; double y = p[j].y; double r = p[j].r; double PtoL = fabs(A*x-y)/di; if(PtoL > r) continue; double AA = k*k+1.0; double BB = -(2.0*x+2.0*k*y); double CC = x*x + y*y - r*r; if(BB*BB-4.0*AA*CC <= 0.0) continue; double jie1x = (-BB+sqrt(BB*BB-4.0*AA*CC))/(2.0*AA); double jie1y = k*jie1x; double jie2x = (-BB-sqrt(BB*BB-4.0*AA*CC))/(2.0*AA); double jie2y = k*jie2x; int P1 = getPlane(jie1x,jie1y); int P2 = getPlane(jie2x,jie2y); if(P1 == Plane && P2 == Plane) sum += 2.0*sqrt(r*r-PtoL*PtoL); else if(P1 == Plane) sum += dis(jie1x,jie1y); else if(P2 == Plane) sum += dis(jie2x,jie2y); } maxi = max(maxi,sum); } //up double sum = 0.0; for(j=0;j<n;j++) { double x = p[j].x; double y = p[j].y; double r = p[j].r; double PtoL = x; if(PtoL > r) continue; double AA = 1.0; double BB = -2.0*y; double CC = x*x + y*y - r*r; double jie1x = 0.0; double jie1y = (-BB+sqrt(BB*BB-4.0*AA*CC))/(2.0*AA); double jie2x = 0.0; double jie2y = (-BB-sqrt(BB*BB-4.0*AA*CC))/(2.0*AA); if(jie1y > 0 && jie2y > 0) sum += fabs(jie1y-jie2y); else if(jie1y > 0) sum += jie1y; else if(jie2y > 0) sum += jie2y; } maxi = max(maxi,sum); //down sum = 0.0; for(j=0;j<n;j++) { double x = p[j].x; double y = p[j].y; double r = p[j].r; double PtoL = x; if(PtoL > r) continue; double AA = 1.0; double BB = -2.0*y; double CC = x*x + y*y - r*r; double jie1x = 0.0; double jie1y = (-BB+sqrt(BB*BB-4.0*AA*CC))/(2.0*AA); double jie2x = 0.0; double jie2y = (-BB-sqrt(BB*BB-4.0*AA*CC))/(2.0*AA); if(jie1y < 0 && jie2y < 0) sum += fabs(jie1y-jie2y); else if(jie1y < 0) sum += -jie1y; else if(jie2y < 0) sum += -jie2y; } maxi = max(maxi,sum); //right sum = 0.0; for(j=0;j<n;j++) { double x = p[j].x; double y = p[j].y; double r = p[j].r; double PtoL = y; if(PtoL > r) continue; double AA = 1.0; double BB = -2.0*x; double CC = x*x + y*y - r*r; double jie1x = (-BB+sqrt(BB*BB-4.0*AA*CC))/(2.0*AA); double jie1y = 0.0; double jie2x = (-BB-sqrt(BB*BB-4.0*AA*CC))/(2.0*AA); double jie2y = 0.0; if(jie1x > 0 && jie2x > 0) sum += fabs(jie1x-jie2x); else if(jie1x > 0) sum += jie1x; else if(jie2x > 0) sum += jie2x; } maxi = max(maxi,sum); //left sum = 0.0; for(j=0;j<n;j++) { double x = p[j].x; double y = p[j].y; double r = p[j].r; double PtoL = y; if(PtoL > r) continue; double AA = 1.0; double BB = -2.0*x; double CC = x*x + y*y - r*r; double jie1x = (-BB+sqrt(BB*BB-4.0*AA*CC))/(2.0*AA); double jie1y = 0.0; double jie2x = (-BB-sqrt(BB*BB-4.0*AA*CC))/(2.0*AA); double jie2y = 0.0; if(jie1x < 0 && jie2x < 0) sum += fabs(jie1x-jie2x); else if(jie1x < 0) sum += -jie1x; else if(jie2x < 0) sum += -jie2x; } maxi = max(maxi,sum); printf("%.3lf\n",maxi); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。