【poj2451】Uyuw's Concert

2015.03.13 18:16 Fri | 0次阅读 | 旧日oi | 固定链接 | 源码

半平面交+求面积,注意最后的处理

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define maxn 40010
#define eps 1e-10
#define DCMP(a) (fabs(a)<eps?1:0)
using namespace std;
struct Point{
    double x,y;
    Point (double _=0.0,double __=0.0):x(_),y(__) {}
    Point operator +(const Point &a)const{
        return Point(x+a.x,y+a.y);
    }
    Point operator -(const Point &a) const{
        return Point(x-a.x,y-a.y);
    }
    Point operator * (double a) const{
        return Point(x*a,y*a);
    }
    void operator +=(const Point &a){
        x+=a.x;y+=a.y;
    }
    void read(){
        scanf("%lf%lf",&x,&y);
    }
}point[maxn],p[maxn];
struct Line{
    Point p,v;
    double alpha;
    bool operator < (const Line &a) const{
        return alpha<a.alpha;
    }
    void read()
    {
        p.read();v.read();
        v=v-p;
        alpha=atan2(v.y,v.x);
    }
    Line (Point a,Point b):p(a),v(b){
        alpha=atan2(v.y,v.x);
    }
    Line(){}
}line[maxn],q[maxn];
int n;
double cross(const Point &a,const Point &b);
bool onleft(const Line &l,const Point &p);
double halfplaneintersection();
Point get_intersection(const Line &a,const Line &b);
void Init();
int main()
{
    Init();
    scanf("%d",&n);n+=4;
        for(int i=5;i<=n;i++) 
        line[i].read();
        sort(line+1,line+n+1);
        printf("%.1lf\n",halfplaneintersection());
    return 0;
}
void Init()
{
    line[1]=Line(Point(0.0,0.0),Point(10000.0,0));
    line[2]=Line(Point(10000.0,0.0),Point(0,10000.0));
    line[3]=Line(Point(10000.0,10000.0),Point(-10000.0,0.0));
    line[4]=Line(Point(0,10000.0),Point(0.0,-10000.0));
}
double cross(const Point &a,const Point &b)
{
    return a.x*b.y-a.y*b.x;
}
bool onleft(const Line &l,const Point &p)
{
    return cross(l.v,p-l.p)>0;
}
double halfplaneintersection()
{
    int front=1,tail=1;
    double area=0.0;
    q[1]=line[1];
    for(int i=2;i<=n;i++)
    {
        while(front<tail&&!onleft(line[i],p[tail-1])) tail--;
        while(front<tail&&!onleft(line[i],p[front])) front++;
        if(DCMP(cross(line[i].v,q[tail].v))) 
        q[tail]=onleft(q[tail],line[i].p)?line[i]:q[tail];
        else q[++tail]=line[i];
        if(front<tail) p[tail-1]=get_intersection(q[tail],q[tail-1]);
    }
    while(front<tail&&!onleft(q[front],p[tail-1])) tail--;
    if(front==tail) return 0;
    p[tail]=get_intersection(q[tail],q[front]);
    for(int i=front;i<tail;i++) area+=cross(p[i],p[i+1]);
    area+=cross(p[tail],p[front]);
    return fabs(area/2.0);
}
Point get_intersection(const Line &a,const Line &b)
{
    Point u=a.p-b.p;
    double tmp=cross(b.v,u)/cross(a.v,b.v);
    return a.p+a.v*tmp;
}```