既见君子

同济医学生的起落落落落人生记录

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;
}

评论
©既见君子
Powered by LOFTER