注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

ural1058 终于过了  

2012-09-20 13:58:31|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
算法是简单暴力的三分
三分精度问题其实不大
犯了个小错误然后WA在test6没完没了
好歹今天中午检查了一遍程序,看了网上的某代码,改了下精度
最终AC了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;

typedef double ld;
const int MAX=10000+10;
const ld EPS=1e-8;
const ld INF=1e60;

int n,st[MAX],top;
ld S,ans;

struct point
{
ld x,y;
point(){}
point(ld a,ld b){x=a;y=b;}
void print()
{
printf("%lf %lf\n",x,y);
}
}d[MAX],temp[MAX];

bool operator == (const point& a,const point& b)
{
return a.x==b.x && a.y==b.y;
}

bool operator < (const point& a,const point& b)
{
if(a.x!=b.x)return a.x<b.x;
else return a.y<b.y;
}

ld chaji(const point& s,const point& a,const point& b)
{
return (a.x-s.x)*(b.y-s.y)-(a.y-s.y)*(b.x-s.x);
}

ld sqr(ld x)
{
return x*x;
}

ld dist(const point& a,const point& b)
{
return sqr(a.x-b.x)+sqr(a.y-b.y);
}

ld getarea(point s,point b,point c,point d)
{
return fabs( chaji(s,b,c)+chaji(s,c,d) );
}

ld work(point s,point b,point c,point d,ld delta)
{
if(getarea(s,b,c,d)+EPS<delta)
return INF;
ld k=chaji(s,b,c);
if(delta+EPS<fabs(k))
return INF;
ld e=chaji(s,c,d);
ld right=fabs((delta-fabs(k))/e);
point np=point( (d.x-c.x)*right+c.x,(d.y-c.y)*right+c.y );
return dist(s,np);
}

ld calc(point a,point b,point c,point d,ld delta)
{
ld left=0,right=1.0,mid1,mid2,ans=INF,w1,w2;

if(fabs(chaji(b,c,d))<delta)
{
ld k=delta-fabs(chaji(b,c,d));
right=1-fabs(k/chaji(a,b,d))-EPS;
}

if(fabs(chaji(a,b,c))>delta)
left=1-fabs(delta/chaji(a,b,c))+EPS;

point np1,np2;
while(1)
{
mid1=(left*2+right)/3;mid2=(left+right*2)/3;

np1=point((b.x-a.x)*mid1+a.x,(b.y-a.y)*mid1+a.y);
np2=point((b.x-a.x)*mid2+a.x,(b.y-a.y)*mid2+a.y);

w1=work(np1,b,c,d,delta);w2=work(np2,b,c,d,delta);
ans=min(ans,w1);ans=min(ans,w2);

if(fabs(w1-w2)<EPS && fabs(right-left)<EPS)
break;

if(w1<w2)
right=mid2;
else left=mid1;
}
return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,A,B,C,D;
ld SAB,SCD;
ans=INF;
scanf("%d",&n);
for(i=0;i<n;++i)
scanf("%lf%lf",&d[i].x,&d[i].y);
d[n]=d[0];
for(i=0;i<n;++i)
S+=chaji(point(0,0),d[i],d[i+1]);
S=fabs(S);
for(A=0;A<n;++A)
{
SAB=0;D=(A+n-1)%n;
for(B=(A+1)%n;1;B=(B+1)%n)
{
if(SAB>S/2)break;
C=(B+1)%n;
SCD=S-SAB-fabs(chaji(d[A],d[B],d[C]))-fabs(chaji(d[A],d[C],d[D]));
if(SCD<=S/2)
ans=min(ans, calc( d[D],d[A],d[B],d[C],S/2-SAB) );
SAB+=fabs(chaji(d[A],d[B],d[C]));
}
}
ans=sqrt(ans);
cout.setf(ios::fixed);
cout.precision(4);
cout<<ans<<endl;
}





  评论这张
 
阅读(227)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018