首页 > 代码库 > csu 1812: 三角形和矩形 凸包

csu 1812: 三角形和矩形 凸包

传送门:csu 1812: 三角形和矩形

思路:首先,求出三角形的在矩形区域的顶点,矩形在三角形区域的顶点。然后求出所有的交点。这些点构成一个凸包,求凸包面积就OK了。 

/**************************************************************    Problem:    User: youmi    Language: C++    Result: Accepted    Time:    Memory:****************************************************************///#pragma comment(linker, "/STACK:1024000000,1024000000")//#include<bits/stdc++.h>#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <map>#include <stack>#include <set>#include <sstream>#include <cmath>#include <queue>#include <deque>#include <string>#include <vector>#define zeros(a) memset(a,0,sizeof(a))#define ones(a) memset(a,-1,sizeof(a))#define sc(a) scanf("%d",&a)#define sc2(a,b) scanf("%d%d",&a,&b)#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)#define scs(a) scanf("%s",a)#define sclld(a) scanf("%I64d",&a)#define pt(a) printf("%d\n",a)#define ptlld(a) printf("%I64d\n",a)#define rep(i,from,to) for(int i=from;i<=to;i++)#define irep(i,to,from) for(int i=to;i>=from;i--)#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))#define lson (step<<1)#define rson (lson+1)#define eps 1e-6#define oo 0x3fffffff#define TEST cout<<"*************************"<<endlconst double pi=4*atan(1.0);using namespace std;typedef long long ll;template <class T> inline void read(T &n){    char c; int flag = 1;    for (c = getchar(); !(c >= 0 && c <= 9 || c == -); c = getchar()); if (c == -) flag = -1, n = 0; else n = c - 0;    for (c = getchar(); c >= 0 && c <= 9; c = getchar()) n = n * 10 + c - 0; n *= flag;}ll Pow(ll base, ll n, ll mo){    if (n == 0) return 1;    if (n == 1) return base % mo;    ll tmp = Pow(base, n >> 1, mo);    tmp = (ll)tmp * tmp % mo;    if (n & 1) tmp = (ll)tmp * base % mo;    return tmp;}//***************************int n;const int maxn=100000+10;const ll mod=1000000007;double xx[10],yy[10];int sgn(double x){    if(fabs(x)<eps)        return 0;    if(x<0)        return -1;    else        return 1;}struct point{    double x,y;    point(){};    point(double _x,double _y)    {        x=_x,y=_y;    }    point operator-(const point &_b)const    {        return point(x-_b.x,y-_b.y);    }    double operator *(const point &_b)const    {        return x*_b.x+y*_b.y;    }    double operator^(const point &_b)const    {        return x*_b.y-_b.x*y;    }    bool operator==(const point &_b)const    {        return sgn(x-_b.x)==0&&sgn(y-_b.y)==0;    }};point tri[10],rec[10];double dist(point a,point b){    return sqrt((a-b)*(a-b));}struct line{    point s, e;    line() {}    line(point _s, point _e)    {        s = _s;        e = _e;    }    pair<int, point> operator &(const line &b)const    {        point res = s;        if(sgn((s - e) ^ (b.s - b.e)) == 0) {            if(sgn((s - b.e) ^ (b.s - b.e)) == 0)                return make_pair(0, res); //重合            else return make_pair(1, res); //平行        }        long double t = ((s - b.s) ^ (b.s - b.e)) / ((s - e) ^ (b.s - b.e));        res.x += (e.x - s.x) * t;        res.y += (e.y - s.y) * t;        return make_pair(2, res);    }};point lst[maxn];int stc[maxn],top;bool _cmp(point p1,point p2){    double temp=(p1-lst[0])^(p2-lst[0]);    if(sgn(temp)>0)        return true;    else if(sgn(temp)==0&&sgn(dist(p1,lst[0])-dist(p2,lst[0]))<=0)        return true;    else        return false;}bool on_line(point p,line uu){    return (sgn(p.x-uu.s.x)*sgn(p.x-uu.e.x))<=0&&(sgn(p.y-uu.s.y)*sgn(p.y-uu.e.y)<=0);}void graham(){    if(n==0)    {        top=0;        return;    }    point p0=lst[0];    int k=0;    for(int i=1;i<n;i++)    {        if((p0.y>lst[i].y)||(p0.y==lst[i].y&&p0.x>lst[i].x))        {            p0=lst[i];            k=i;        }    }    swap(lst[k],lst[0]);    sort(lst+1,lst+n,_cmp);    if(n==1)    {        top=1;        stc[0]=0;        return ;    }    top=2;    stc[0]=0;    stc[1]=1;    if(n==2)        return ;    for(int i=2;i<n;i++)    {        while(top>1&&sgn((lst[stc[top-1]]-lst[stc[top-2]])^(lst[i]-lst[stc[top-2]]))<=0)            top--;        stc[top++]=i;    }}bool in_tri(point p){    double s=fabs((tri[0]-tri[1])^(tri[0]-tri[2]));    double s1=fabs((p-tri[0])^(p-tri[1]));    double s2=fabs((p-tri[1])^(p-tri[2]));    double s3=fabs((p-tri[2])^(p-tri[0]));    return sgn(s1+s2+s3-s)==0;}bool in_rec(point p){    return sgn(p.x-xx[3])>=0&&sgn(p.x-xx[4])<=0&&sgn(p.y-yy[3])>=0&&sgn(p.y-yy[4])<=0;}int main(){    #ifndef ONLINE_JUDGE    freopen("in.txt","r",stdin);    #endif    while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf",xx+1,yy+1,xx+2,yy+2,xx+3,yy+3,xx+4,yy+4))    {        tri[0]=point(xx[1],yy[1]),tri[1]=point(xx[1],yy[2]),tri[2]=point(xx[2],yy[1]);        rec[0]=point(xx[3],yy[3]),rec[1]=point(xx[3],yy[4]),rec[2]=point(xx[4],yy[4]),rec[3]=point(xx[4],yy[3]);        n=0;        rep(i,0,3)            if(in_tri(rec[i]))                lst[n++]=rec[i];        rep(i,0,2)            if(in_rec(tri[i]))                lst[n++]=tri[i];        rep(i,0,3)        {            line gg=line(rec[i],rec[(i+1)%4]);            rep(j,0,2)            {                line hh=line(tri[j],tri[(j+1)%3]);                pair<int, point> res=hh&gg;                if(res.first==2)                {                    point &uu=res.second;                    if(on_line(uu,gg)&&on_line(uu,hh))                        lst[n++]=uu;                }            }        }        sort(lst,lst+n,_cmp);        n=unique(lst,lst+n)-lst;        graham();        double ans=0;        if(top>=3)        {            rep(i,0,top-1)            {                ans+=lst[stc[i]]^lst[stc[(i+1)%top]];            }        }        ans/=2;        printf("%.7f\n",ans);    }}

 

csu 1812: 三角形和矩形 凸包