表示这个题目很坑,竟然普通的枚举角度也能过,在现场如果没敢这么干的童鞋肯定后悔死了,不过直接枚举跑的时间还是没三分枚举快的
三分枚举的思想其实和二分差不多,具体为什么对,看看代码是怎么枚举的,稍微想想就能明白了!
直接枚举:
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #define eps 1e-8 using namespace std; #define PI acos(-1.0) struct point { double x; double y; point(double a=0,double b=0):x(a),y(b){} }a,b,c,d,pos,temp1,temp2,start; double r; double cross(point p0, point p1, point p2)//j计算差乘 { return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);} double dis(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double disptoseg(point p,point l1,point l2) { point t=p; t.x+=l1.y-l2.y,t.y+=l2.x-l1.x; if(cross(l1,t,p)*cross(l2,t,p)>eps) return dis(p,l1) < dis(p,l2) ? dis(p,l1):dis(p,l2); return fabs(cross(p,l1,l2)/dis(l1,l2)); } double distotri(point p) { return min(disptoseg(p,a,b),min(disptoseg(p,b,d),min(disptoseg(p,d,c),disptoseg(p,c,a)))); } point make_p(double l) { return point(pos.x+r*cos(l),pos.y+r*sin(l)); } double find_dis(point p) { return dis(p,start)+distotri(p); } double find_ans() { double ans=1e10; double mid=0; double over=PI*2,k; point p; for(mid=0;mid<=over;mid+=1e-3) { p=make_p(mid); k=find_dis(p); if(ans > k) ans=k; } return ans; } int main() { while(scanf("%lf%lf",&start.x,&start.y)) { if(start.x==0 && start.y==0) return 0; scanf("%lf%lf%lf",&pos.x,&pos.y,&r); scanf("%lf%lf%lf%lf",&temp1.x,&temp1.y,&temp2.x,&temp2.y); if(temp1.x > temp2.x) c=temp1,temp1=temp2,temp2=c; if(temp1.y > temp2.y) a=temp1,d=temp2,b.x=d.x,b.y=a.y,c.x=a.x,c.y=d.y; else c=temp1,b=temp2,a.x=c.x,a.y=b.y,d.x=b.x,d.y=c.y; printf("%.2lf\n",find_ans()); } return 0; }
三分枚举:
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #define eps 1e-8 using namespace std; #define PI acos(-1.0) struct point { double x; double y; point(double a=0,double b=0):x(a),y(b){} }a,b,c,d,pos,temp1,temp2,start; double r; double cross(point p0, point p1, point p2)//j计算差乘 { return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);} double dis(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double disptoseg(point p,point l1,point l2) { point t=p; t.x+=l1.y-l2.y,t.y+=l2.x-l1.x; if(cross(l1,t,p)*cross(l2,t,p)>eps) return dis(p,l1) < dis(p,l2) ? dis(p,l1):dis(p,l2); return fabs(cross(p,l1,l2)/dis(l1,l2)); } double distotri(point p) { return min(disptoseg(p,a,b),min(disptoseg(p,b,d),min(disptoseg(p,d,c),disptoseg(p,c,a)))); } point make_p(double l) { return point(pos.x+r*cos(l),pos.y+r*sin(l)); } double find_dis(point p) { return dis(p,start)+distotri(p); } double find_ans() { double l,r,ans1,ans2,t_2,t_4; l=0,r=PI; double mid_2,mid_4; point p_2,p_4; while(r-l>=eps) { mid_2=(l+r)/2; mid_4=(mid_2+r)/2; p_2=make_p(mid_2); p_4=make_p(mid_4); t_2=find_dis(p_2); t_4=find_dis(p_4); if(t_2 > t_4) l=mid_2; else r=mid_4; } p_2=make_p(l); ans1=find_dis(p_2); l=PI,r=PI*2; while(r-l>=eps) { mid_2=(l+r)/2; mid_4=(mid_2+r)/2; p_2=make_p(mid_2); p_4=make_p(mid_4); t_2=find_dis(p_2); t_4=find_dis(p_4); if(t_2 > t_4) l=mid_2; else r=mid_4; } p_2=make_p(l); ans2=find_dis(p_2); return min(ans1,ans2); } int main() { while(scanf("%lf%lf",&start.x,&start.y)) { if(start.x==0 && start.y==0) return 0; scanf("%lf%lf%lf",&pos.x,&pos.y,&r); scanf("%lf%lf%lf%lf",&temp1.x,&temp1.y,&temp2.x,&temp2.y); if(temp1.x > temp2.x) c=temp1,temp1=temp2,temp2=c; if(temp1.y > temp2.y) a=temp1,d=temp2,b.x=d.x,b.y=a.y,c.x=a.x,c.y=d.y; else c=temp1,b=temp2,a.x=c.x,a.y=b.y,d.x=b.x,d.y=c.y; printf("%.2lf\n",find_ans()); } return 0; }