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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1043][HAOI2008]下落的圆盘  

2014-10-14 23:14:46|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1043: [HAOI2008]下落的圆盘

奇怪的计算几何题
说实话思路没什么难的只是写起来比较蛋疼
被题目描述坑了导致wa了一次(?QдQ)b
圆的所有信息都是小数
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 1000+10;
int n,m,ln;
int scan(){int i;scanf("%d",&i);return i;}
struct Point{
double x,y;
Point(){}
Point(double a,double b):x(a),y(b){}
double len(){return sqrt((double)x*x+(double)y*y);}
}up(0,1),line[N*2];
struct cir{
Point d;
double r;
cir(){}
cir(Point a,double c):d(a),r(c){}
}data[N];
Point operator - (Point a,Point b){return Point(a.x - b.x,a.y - b.y);}
Point operator + (Point a,Point b){return Point(a.x + b.x,a.y + b.y);}
Point operator * (Point a,double b){return Point(a.x*b,a.y*b);}
Point dw(Point a){return a*(1/a.len());}
double p2(double a){return a*a;}
Point normal(Point a){double l = a.len();return Point(-a.y/l,a.x/l);}
double corss(Point a,Point b){return a.x*b.y - b.x*a.y;}
double dot(Point a,Point b){return a.x*b.x + a.y*b.y;}
double getrad(Point a,Point b){
a = dw(a);b = dw(b);
double rcos,rsin;
rcos = acos(dot(a,b));rsin = asin(corss(a,b));
if(rsin > 0)return M_PI*2 - rcos;
else return rcos;
}
bool line_cmp(Point a,Point b){if(a.x==b.x)return a.y > b.y;return a.x < b.x;}
const double eps = 1e-9;
bool dcmp(double a,double b){return fabs(a-b) < eps;}
double calc(int x){
double sub=0,r1 = data[x].r,r2;
double last = 0,d,len,l,r;
Point v,mid,add;ln = 0;
for(int i=x+1;i<=n;i++){
if((d=(v=data[i].d - data[x].d).len()) >= r1+(r2=data[i].r))continue;
if(fabs(r1-r2) >= d){
if(r1 > r2) continue;
else return 0;
}
/*
if(r2 > r1 && r2 > d)
//2 - left
len = -(p2(r2)-p2(r1)-p2(d))/(2*d);
else
//1&3 - mid & right
len = (p2(r1)-p2(r2)+p2(d))/(2*d);*/
len = (p2(r1)-p2(r2)+p2(d))/(2*d);
mid = v*(len/v.len());
len = sqrt(p2(r1) - p2(len));

add = normal(v)*len; // 这里写成 normal(mid)*len会爆
l = getrad(up*r1,mid+add);
add = add*-1;
r = getrad(up*r1,mid+add);
if(l > r){
line[++ln] = Point(0,r);
line[++ln] = Point(l,M_PI*2);
}else line[++ln] = Point(l,r);
}
sort(line+1,line+1+ln,line_cmp);
for(int i=1;i<=ln;i++){
if(line[i].y <= last)continue;
sub+=line[i].y - max(line[i].x,last);
last = line[i].y;
}
return (2*M_PI - sub)*r1;
}
int main(){
//freopen("in.txt","r",stdin);
int i,j;
double a,b,c;
n = scan();
for(i=1;i<=n;i++){
scanf("%lf%lf%lf",&c,&a,&b);
data[i] = cir(Point(a,b),c);
}
double ans = 0,tmp;
for(i=1;i<=n;i++){
tmp = calc(i);
//printf("%f\n",tmp);
ans += tmp;
}
printf("%.3f\n",ans);
return 0;
}

题解:
对于每个圆a,枚举每一个在它之后落下的圆b,计算出覆盖周长并,减掉后就是这个圆对答案的贡献。
但是要怎么算覆盖周长并呢?
首先找两个圆的交点(特判掉不相交,包含的情况),在两圆间连线,然后从交点向上面做垂线,用勾股定理求出圆心到垂足的距离,然后再求一个法向量乘上垂线长度,就可以得到圆心到两个交点的向量。(注意不要对一个可能为0向量的向量求法向量,会爆。)
求出到两个交点的向量后分别计算(0,1)与其的夹角,这样就求出一个夹角区间[l,r],把圆拆成一条线,即如果l>r,就拆成[0,r]和[l,2π]两个。
最后对每个"线"按照左端点排序,求一下长度并就行。

另:
由于情况很多,所以勾股定理解方程的时候需要分类讨论。
基本上是相交的所有情况,左边的是圆a,右边的是圆b
[BZOJ1043][HAOI2008]下落的圆盘 - 时光机 - 时光机TimeMachine
 
再精简一下,分成以下三种情况:1.垂心在圆心连线之间2.垂心在圆b那一边的外面3.垂心在圆a那一边的外面
然后我分别列出式子发现1&2这两种情况的方程化简之后是一样的,3不太一样。
结果无意间发现前两种的方程放到第三种情况里也可以得到正确答案……不太清楚为什么
liangjs的解释是说因为圆的方程是一定的所以你解出的东西是对的(但是我想说我用的向量+勾股定理乱搞啊……)
  评论这张
 
阅读(151)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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