hdu 4454 Stealing a Cake 三分法

很容易想到三分法求解,不过要分别在0-pi,pi-2pi进行三分。

另外也可以直接暴力枚举……

代码如下:

 #include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 50000
using namespace std;
struct point
{
double x,y;
point(double _x=,double _y=){
x=_x;
y=_y;
}
point operator-(point a){
return point(x-a.x,y-a.y);
}
point operator+(point a){
return point(x+a.x,y+a.y);
}
double operator*(point a){
return (x*a.x+y*a.y);
}
}p1,p2,p;
double x,y,r;
double dis2(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double dis(point a, point b, point c)
{
point ab = b - a;
point ac = c - a;
double f = ab*ac;
if (f<) return dis2(c, a);//C1处的点
double d = ab*ab;
if ( f>d) return dis2(c, b);//C2处的点,d=f*cos(theta)
f = f/d;
ab.x*=f;ab.y*=f;
point D = a + ab; // c在ab线段上的投影点
return dis2(c, D);
}
double line(point a)
{
point b,c;
b.x=min(p1.x,p2.x);
b.y=max(p1.y,p2.y);
c.x=max(p1.x,p2.x);
c.y=min(p1.y,p2.y);
double MIN1,MIN2;
MIN1=min(dis(p2,c,a),dis(p1,c,a));
MIN2=min(dis(p1,b,a),dis(p2,b,a));
return min(MIN1,MIN2);
}
point get(double a)
{
return point(x+r*cos(a),y+r*sin(a));
}
double solve()
{
double r,l,mid,midmid,t1,t2,ans1,ans2;
point m1,m2;
r=pi;l=;
while(r-l>=1e-){
mid=(r+l)/;
midmid=(mid+r)/;
m1=get(mid);
m2=get(midmid);
t1=line(m1)+dis2(m1,p);
t2=line(m2)+dis2(m2,p);
if(t1>t2) l=mid;
else r=midmid;
}
ans1=t1;
r=*pi;l=pi;
while(r-l>=1e-){
mid=(r+l)/;
midmid=(mid+r)/;
m1=get(mid);
m2=get(midmid);
t1=line(m1)+dis2(m1,p);
t2=line(m2)+dis2(m2,p);
if(t1>t2) l=mid;
else r=midmid;
}
ans2=t1;
return min(ans1,ans2);
}
int main(){
while(cin>>p.x>>p.y){
if(fabs(p.x)<1e-&&fabs(p.y)<1e-) break;
cin>>x>>y>>r>>p1.x>>p1.y>>p2.x>>p2.y;
point temp;
temp.x=p1.x;temp.y=p1.y;
p1.x=min(p1.x,p2.x);p1.y=min(p1.y,p2.y);
p2.x=max(temp.x,p2.x);p2.y=max(temp.y,p2.y);
printf("%.2lf\n",solve());
}
return ;
}
上一篇:Linux修改文件时候出现崩溃,产生了一个.swap交换文件,如何修复?


下一篇:Codeforce - Street Lamps