HihoCoder - 1652：三角形面积和2（扫描线）

题意：给定X轴上的一些三角形，求面积并。每个三角形的给出形式是Li,Ri,Xi,Yi，表示三个顶点分别是(Li,0)；(Ri,0)；(Xi,Yi)，且满足Li<=Xi<=Ri；

思路：我们把这些三角形全部涂黑，就会发现只需要找到这些关键的“拐点”即可，最后求出每两个拐点之间形成的梯形的面积即可。那么为了找拐点，我们需要把所有的X求出来，然后用这些X和线段树求交点，每个X保留一个最高的Y，这个就是拐点了。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

typedef long long ll;

const double eps=1e-;

const double pi=acos(-1.0);

struct point{

    double x,y;

    point(double a=,double b=):x(a),y(b){}

};

int dcmp(double x){ return fabs(x)<eps?:(x<?-:);}

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 p){ return point(A.x*p,A.y*p);}

point operator /(point A,double p){ return point(A.x/p,A.y/p);}

point rotate(point A,double rad){ //向量的旋转

    return point(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));

}

bool operator ==(const point& a,const point& b) {

     return dcmp(a.x-b.x)==&&dcmp(a.y-b.y)==;

}

double dot(point A,point B){ return A.x*B.x+A.y*B.y;}

double det(point A,point B){ return A.x*B.y-A.y*B.x;}

double dot(point O,point A,point B){ return dot(A-O,B-O);}

double det(point O,point A,point B){ return det(A-O,B-O);}

double length(point A){ return sqrt(dot(A,A));}

double angle(point A,point B){ return acos(dot(A,B)/length(A)/length(B));} //夹角

point jiaopoint(point p,point v,point q,point w) //如果平行，除0会有问题

{   //p+tv q+tw，点加向量表示直线，求直线交点

    //如果是线段，还应该实现判定是否相离或者平行

    point u=p-q;

    double t=det(w,u)/det(v,w);

    return p+v*t;

}

point GetCirPoint(point a,point b,point c)

{

    point p=(a+b)/;    //ab中点

    point q=(a+c)/;    //ac中点

    point v=rotate(b-a,pi/2.0),w=rotate(c-a,pi/2.0);   //中垂线的方向向量

    if (dcmp(length(det(v,w)))==)    //平行

    {

        if(dcmp(length(a-b)+length(b-c)-length(a-c))==) return (a+c)/;

        if(dcmp(length(b-a)+length(a-c)-length(b-c))==) return (b+c)/;

        if(dcmp(length(a-c)+length(c-b)-length(a-b))==) return (a+b)/;

    }

    return jiaopoint(p,v,q,w);

}

int main()

{

}

当然也可以直接套多边形面积并的板子：

#include<bits/stdc++.h>

using namespace std;

#define mp make_pair

typedef long long ll;

const double inf=1e200;

const double eps=1e-;

const double pi=*atan(1.0);

int dcmp(double x){ return fabs(x)<eps?:(x<?-:);}

struct point{

    double x,y;

    point(double a=,double b=):x(a),y(b){}

};

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 p){ return point(A.x*p,A.y*p);}

point operator /(point A,double p){ return point(A.x/p,A.y/p);}

bool operator ==(const point& a,const point& b){

    return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;

}

double dot(point A,point B){ return A.x*B.x+A.y*B.y;}

double det(point A,point B){ return A.x*B.y-A.y*B.x;}

double det(point O,point A,point B){ return det(A-O,B-O);}

double length(point A){ return sqrt(dot(A,A));}

double area(vector<point>p){

    double ans=; int sz=p.size();

    for(int i=;i<sz-;i++) ans+=det(p[i]-p[],p[i+]-p[]);

    return ans/2.0;

}

double seg(point O,point A,point B){

    if(dcmp(B.x-A.x)==) return (O.y-A.y)/(B.y-A.y);

    return (O.x-A.x)/(B.x-A.x);

}

vector<point>pp[];

pair<double,int>s[*];

double polyunion(vector<point>*p,int N){ //需要这些点是顺时针

    double res=;

    for(int i=;i<N;i++){

        int sz=p[i].size();

        for(int j=;j<sz;j++){

            int m=;

            s[m++]=mp(,);

            s[m++]=mp(,);

            point a=p[i][j],b=p[i][(j+)%sz];

            for(int k=;k<N;k++){

                if(i!=k){

                    int sz2=p[k].size();

                    for(int ii=;ii<sz2;ii++){

                        point c=p[k][ii],d=p[k][(ii+)%sz2];

                        int c1=dcmp(det(b-a,c-a));

                        int c2=dcmp(det(b-a,d-a));

                        if(c1==&&c2==){

                            if(dcmp(dot(b-a,d-c))){

                                s[m++]=mp(seg(c,a,b),);

                                s[m++]=mp(seg(c,a,b),-);

                            }

                        }

                        else{

                            double s1=det(d-c,a-c);

                            double s2=det(d-c,b-c);

                            if(c1>=&&c2<) s[m++]=mp(s1/(s1-s2),);

                            else if(c1<&&c2>=) s[m++]=mp(s1/(s1-s2),-);

                        }

                    }

                }

            }

            sort(s,s+m);

            double pre=min(max(s[].first,0.0),1.0),now,sum=;

            int cov=s[].second;

            for(int j=;j<m;j++){

                now=min(max(s[j].first,0.0),1.0);

                if(!cov) sum+=now-pre;

                cov+=s[j].second;

                pre=now;

            }

            res+=det(a,b)*sum;

        }

    }

    return res/;

}

int main()

{

    int N,M,i,j; point tp,ta,tb; ta.y=tb.y=0.0;

    scanf("%d",&N);

    for(i=;i<N;i++){

        scanf("%lf%lf%lf%lf",&ta.x,&tb.x,&tp.x,&tp.y);

        pp[i].push_back(tb);

        pp[i].push_back(ta);

        pp[i].push_back(tp);

    }

    double t1=,t2=polyunion(pp,N);

    for(i=;i<N;i++) t1+=area(pp[i]);

    printf("%.2lf\n",-t2);

    return ;

}

巴特西

HihoCoder - 1652：三角形面积和2（扫描线）

最新文章

热门文章