oj7 kao
刚出炉的kao又来啦！有没有人注意到我其实是写过这道题的呼呼
不如来讲一个欢乐的故事吧，今天呢，有一个蠢蠢的女孩子（以下简称L）看到poj一道圆和多边形求交的题（3675）！“正好在练面积交并呢不如写一写咯！”L如此naive的想到，于是捣鼓了一下午终于写出来了！然后交到poj上去的result居然是O！L！E！，L一点也不明白为什么，在和网上标程对拍了三角形之后也没发现任何问题，在裸眼调了许久之后终于抱住了LPX的大腿。
友善的LPX似乎也从来没遇见过OLE于是- -就用他A过思考熊的kao来交了这道题发现本机编译能过交上去居然CE- -最后把编译器改成G++之后终于不CE了，但是却遭受了和L一样的结果！OLE！于是L和LPX陷入了深度思考，最后决定让poj背锅嘤嘤。
不过也是蛮好的呢，当初kao我挂了一点精度，有两个点过不了，现在也算是能够A了呢，少一个Naive就少一个咯～
//题解：根据圆心三角剖分然后算每一个三角形与扇形的交点，分五种情况讨论，正负由叉积来决定
code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100+5;
#define eps 1e-7
int n;
double R;
int sgn(double v){
if(fabs(v)<eps) return 0;
return v>0?1:-1;
}
struct Point{
double x,y;
void read(){
scanf("%lf%lf",&x,&y);
}
void print(){
printf("%.6f %.6f\n",x,y);
}
Point(double _x=0,double _y=0){x=_x,y=_y;}
Point operator +(const Point &c){
return Point(x+c.x,y+c.y);
}
Point operator -(const Point &c){
return Point(x-c.x,y-c.y);
}
Point operator *(const double &c){
return Point(x*c,y*c);
}
Point operator /(const double &c){
if(!sgn(c)) return Point(x,y);
return Point(x/c,y/c);
}
double len(){
return sqrt(x*x+y*y);
}
} s[maxn];
bool ins(Point &a){
return sgn(a.len()-R)<=0;
}
double det(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
double dot(Point a,Point b){
return a.x*b.x+a.y*b.y;
}
double lk(double alpha){
return alpha/2*R*R;
}
double dis(Point a,Point b){
double d=dot(a*-1,b-a)/(b-a).len();
return sqrt(a.len()*a.len()-d*d);
}
typedef Point Vector;
bool in(Point a,Point b,Point c){
return sgn(a.x-max(b.x,c.x))<=0&&sgn(a.x-min(b.x,c.x))>=0&&sgn(a.y-max(b.y,c.y))<=0&&sgn(a.y-min(b.y,c.y))>=0;
}
bool insect(Point &a,Point &b,Point &c,Point &d){
double D=dis(a,b);
Vector dir=b-a;
double len=dot(a*-1,dir)/dir.len();
dir=dir/dir.len()*len;
Point mid=a+dir;
len=sqrt(R*R-D*D);
dir=(b-a)/(b-a).len();
Point l=mid+dir*len;
Point r=mid-dir*len;
// l.print();
// r.print();
if(in(l,a,b)&&in(r,a,b)){
c=l,d=r;
return true;
}
else if(in(l,a,b)){
c=l;
return true;
}
else if(in(r,a,b)){
c=r;
return true;
}
else return false;
}
double ang(Point a,Point b){
// a.print(),b.print();
// cout<<acos(dot(a,b)/a.len()/b.len())<<endl;
return acos(dot(a,b)/a.len()/b.len());
}
double outside(Point &a,Point &b){
Point zzk,cx;
if(sgn(dis(a,b)-R)>=0||!insect(a,b,zzk,cx)) return lk(ang(a,b));
double area=fabs(det(zzk,cx)/2);
double alpha=min(ang(a,zzk),ang(a,cx));
area+=lk(alpha);
alpha=min(ang(b,zzk),ang(b,cx));
area+=lk(alpha);
return area;
}
double half(Point &a,Point &b){//保证a是在内部的点
Point zzk,cx;
insect(a,b,zzk,cx);
// zzk.print();
double fan=lk(ang(zzk,b));
double other=fabs(det(zzk,a)/2);
return fan+other;
}
double get(Point &a,Point &b,int f){
if(ins(a)&&ins(b)) return fabs(det(b,a)/2)*f;
if(!ins(a)&&!ins(b)) return outside(a,b)*f;
if(ins(a)) return half(a,b)*f;
else return half(b,a)*f;
}
int main(){
freopen("kao.in","r",stdin);
freopen("kao.out","w",stdout);
while(scanf("%d",&n)!=EOF){
scanf("%lf",&R);
for(int i=1;i<=n;++i) s[i].read();
double ans=0;
for(int i=1;i<=n;++i){
double area=det(s[i],s[i%n+1]);
int tmp=sgn(area);
// cout<<tmp<<endl;
if(tmp) ans+=get(s[i],s[i%n+1],tmp);
}
printf("%.9f\n",fabs(ans));
}
return 0;
}