[CQOI2005]三角形面积并

C++(g++ 7.5.0) 解法, 执行用时: 30ms, 内存消耗: 612K, 提交时间: 2023-08-04 18:51:02

#include<bits/stdc++.h>
#define db double
#define P pair<db,db>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define eps 1e-8
#define INF 0x3f3f3f3f
#define N 110
#define M 100100
using namespace std;

int n,nn,xx;
db ans,zj=666;
bool deb;
struct Node
{
    db x,y;
    void in()
    {
    db p,q;
    scanf("%lf%lf",&p,&q);
    x=cos(zj)*p-sin(zj)*q;
    y=cos(zj)*q+sin(zj)*p;
    }
    Node operator + (const Node &u) const{return (Node){x+u.x,y+u.y};}
    Node operator - (const Node &u) const{return (Node){x-u.x,y-u.y};}
    Node operator * (const db &u) const{return (Node){x*u,y*u};}
    Node operator / (const db &u) const{return (Node){x/u,y/u};}
    bool operator < (const Node u){return x<u.x;}
}node[M];
struct Xn
{
    Node a,v;
    void make(Node p,Node q){a=p,v=q-p;}
}xn[N*3];
struct Sj
{
    Node a,b,c;
}sj[N];
vector<P>use;

inline db cj(Node u,Node v){return u.x*v.y-u.y*v.x;}
inline bool up(Node u,Xn v){return cj(v.a-u,v.a+v.v-u)>0;}
inline bool bet(db u,Xn v)
{
    if(fabs(v.v.x)<eps) return 0;
    return u+eps>min(v.a.x,(v.a+v.v).x) && u<max(v.a.x,(v.a+v.v).x)+eps;
}
inline db xd(db u,Xn v)
{
    if(deb) cout<<"   "<<(v.a+v.v*(u-v.a.x)/v.v.x).y<<endl;
    return (v.a+v.v*(u-v.a.x)/v.v.x).y;
}
inline bool yj(Xn u,Xn v)
{
    if(fabs(cj(v.v,u.v))<eps) return 0;
    return (up(u.a,v)^up(u.a+u.v,v)) && (up(v.a,u)^up(v.a+v.v,u));
}
inline Node jd(Xn u,Xn v)
{
    db t=(cj(u.a,u.v)-cj(v.a,u.v))/cj(v.v,u.v);
    return v.v*t+v.a;
}

inline db ask(db u)
{
    int i,j;
    db res=0,t,r;
    P tmp;
    Xn a,b,c;
    use.clear();
    for(i=1;i<=n;i++)
    {
    a.make(sj[i].a,sj[i].b);
    b.make(sj[i].a,sj[i].c);
    c.make(sj[i].b,sj[i].c);
    if(bet(u,a)+bet(u,b)+bet(u,c)<2) continue;
    tmp.fi=INF,tmp.se=-INF;
    if(bet(u,a)) t=xd(u,a),tmp.fi=min(tmp.fi,t),tmp.se=max(tmp.se,t);
    if(bet(u,b)) t=xd(u,b),tmp.fi=min(tmp.fi,t),tmp.se=max(tmp.se,t);
    if(bet(u,c)) t=xd(u,c),tmp.fi=min(tmp.fi,t),tmp.se=max(tmp.se,t);
    use.pb(tmp);
    }
    sort(use.begin(),use.end());
    for(i=0;i<use.size();i=j)
    {
    r=use[i].se;
    for(j=i+1;j<use.size();j++)
    {
        if(use[j].fi>r) break;
        r=max(r,use[j].se);
    }
    res+=r-use[i].fi;
    }
    return res;
}

int main()
{
    int i,j;
    db p,q;
    cin>>n;
    for(i=1;i<=n;i++)
    {
    sj[i].a.in();
    sj[i].b.in();
    sj[i].c.in();
    xn[++xx].make(sj[i].a,sj[i].b);
    xn[++xx].make(sj[i].a,sj[i].c);
    xn[++xx].make(sj[i].b,sj[i].c);
    node[++nn]=sj[i].a;
    node[++nn]=sj[i].b;
    node[++nn]=sj[i].c;
    }
    for(i=1;i<=xx;i++)
    {
    for(j=i+1;j<=xx;j++)
    {
        if(!yj(xn[i],xn[j])) continue;
        node[++nn]=jd(xn[i],xn[j]);
    }
    }
    sort(node+1,node+nn+1);
    p=ask(node[1].x);
    for(i=1;;i=j)
    {
    for(j=i+1;j<=nn;j++) if(node[j].x-node[i].x>eps) break;
    if(j>nn) break;
    q=ask(node[j].x);
    ans+=(p+q)*(node[j].x-node[i].x)/2.0;
    p=q;
    }
    printf("%.2f",ans-eps);
}

C++11(clang++ 3.9) 解法, 执行用时: 55ms, 内存消耗: 488K, 提交时间: 2019-03-10 17:54:48

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 100005
#define eps 1e-8
using namespace std;
int n,tot,cnt;
double last,ans,pos[maxn];
struct P{double x,y;}p[105][3];
struct L{P a,b;}l[105][3];
struct seg{double l,r;}f[105];
inline P operator -(P a,P b){return (P){a.x-b.x,a.y-b.y};}
inline double operator *(P a,P b){return a.x*b.y-a.y*b.x;}//叉积 
inline double operator /(P a,P b){return a.x*b.x+a.y*b.y;}//点积 
inline P inter(L l1,L l2)
{
	double k1=(l2.b-l1.a)*(l1.b-l1.a),k2=(l1.b-l1.a)*(l2.a-l1.a),t=k1/(k1+k2);
	return (P){l2.b.x+(l2.a.x-l2.b.x)*t,l2.b.y+(l2.a.y-l2.b.y)*t};
}
inline bool judge(L l1,L l2)
{
	return fabs((l1.b.y-l1.a.y)*(l2.b.x-l2.a.x)-(l1.b.x-l1.a.x)*(l2.b.y-l2.a.y))>eps;
}
inline bool cmp(seg a,seg b)
{
	return fabs(a.l-b.l)<=eps?a.r<b.r:a.l<b.l;
}
inline double dcmp(double x)
{
	if (fabs(x)<=eps) return 0;
	else return x<0?-1:1;
}
inline bool cross(P a1,P a2,P b1,P b2)
{
	double c1=(a2-a1)*(b1-a1),c2=(a2-a1)*(b2-a1),c3=(b2-b1)*(a1-b1),c4=(b2-b1)*(a2-b1);
	return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
inline double calc(double x)
{
	L ln=(L){(P){x,0},(P){x,1}};
	int num;
	double y[4],h,ret=0;
	cnt=0;
	F(i,1,n)
	{
		double mn=min(p[i][0].x,min(p[i][1].x,p[i][2].x)),mx=max(p[i][0].x,max(p[i][1].x,p[i][2].x));
		if (x<mn+eps||x>mx-eps) continue;
		num=0;
		F(j,0,2) if (judge(l[i][j],ln))
		{
			P tmp=inter(l[i][j],ln);
			if ((l[i][j].a-tmp)/(l[i][j].b-tmp)>-eps) continue;
			y[++num]=tmp.y;
		}
		if (num>1) f[++cnt]=(seg){y[1],y[2]};
	}
	F(i,1,cnt) if (f[i].l>f[i].r) swap(f[i].l,f[i].r);
	sort(f+1,f+cnt+1,cmp);
	F(i,1,cnt)
	{
		if (i==1||f[i].l>h+eps) ret+=f[i].r-f[i].l,h=f[i].r;
		else if (f[i].r>h+eps) ret+=f[i].r-h,h=f[i].r;
	}
	return ret;
}
int main()
{
	scanf("%d",&n);
	F(i,1,n) F(j,0,2) scanf("%lf%lf",&p[i][j].x,&p[i][j].y),pos[++tot]=p[i][j].x;
	F(i,1,n) l[i][0]=(L){p[i][1],p[i][2]},l[i][1]=(L){p[i][0],p[i][2]},l[i][2]=(L){p[i][0],p[i][1]};
	F(i,1,n-1) F(j,i+1,n) F(k1,0,2) F(k2,0,2)
		if (cross(l[i][k1].a,l[i][k1].b,l[j][k2].a,l[j][k2].b)) pos[++tot]=inter(l[i][k1],l[j][k2]).x;
	sort(pos+1,pos+tot+1);
	last=pos[1];
	F(i,2,tot)
	if (fabs(pos[i]-last)>eps)
	{
		ans+=calc((pos[i]+last)/2)*(pos[i]-last);
		last=pos[i];
	}
	printf("%.2lf\n",ans-eps);
	return 0;
}

详情