面积并

  1. bzoj 1845 Cqoi2005
    1. [Cqoi2005] 三角形面积并
    2. bzoj 1845: [Cqoi2005] 三角形面积并 扫描线
    3. BZOJ 1845 CQOI 2005 三角形面积并 扫描线
    4. BZOJ 1845: [Cqoi2005] 三角形面积并 [计算几何 扫描线]
    5. [lydsy1845][lg4406][CQOI2005]三角形面积并
  2. AcWing 2801
    1. AcWing 2801. 三角形面积并
    2. AcWing 2801. 三角形面积并 [CQOI2005] 扫描线
  3. 圆形并
    1. [lydsy2178][spoj CIRU]圆的面积并
  4. 合集
    1. 【算法专题】平面图形的面积并问题
  5. LeetCode 850
    1. LeetCode | 850. 矩形面积 II
    2. LC 850. 矩形面积 II
    3. 850. 矩形面积 II

我在项目中使用的是 BZOJ 1845: [Cqoi2005] 三角形面积并 [计算几何 扫描线]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//
// main.cpp
// bzoj1845
//
// Created by Candy on 2017/2/1.
// Copyright © 2017年 Candy. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const double eps=1e-8;
const double INF=1e9;
const int N=1005;

inline int sgn(double x){
if(abs(x)<eps) return 0;
else return x<0?-1:1;
}

struct Vector{
double x,y;
Vector(double a=0,double b=0):x(a),y(b){}
bool operator <(const Vector &a)const{
//return x<a.x||(x==a.x&&y<a.y);
return sgn(x-a.x)<0||(sgn(x-a.x)==0&&sgn(y-a.y)<0);
}
void print(){printf("%lf %lf\n",x,y);}
};
typedef Vector Point;
Vector operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
Vector operator -(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
Vector operator *(Vector a,double b){return Vector(a.x*b,a.y*b);}
Vector operator /(Vector a,double b){return Vector(a.x/b,a.y/b);}
bool operator ==(Vector a,Vector b){return sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0;}

double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}


struct Line{
Point s,t;
int id;
Line(){}
Line(Point s,Point t,int i):s(s),t(t),id(i){}
Line(Point s,Point t):s(s),t(t){}
}L[N];
int nl;
Point LI(Line a,Line b){
Vector v=a.s-b.s,v1=a.t-a.s,v2=b.t-b.s;
double t=Cross(v2,v)/Cross(v1,v2);
return a.s+v1*t;
}
bool isLSI(Line l1,Line l2){
Vector v=l1.t-l1.s,u=l2.s-l1.s,w=l2.t-l1.s;
return sgn(Cross(v,u))!=sgn(Cross(v,w));
}
struct Triangle{
Point a,b,c;
Triangle(){}
Triangle(Point a,Point b,Point c):a(a),b(b),c(c){}
}t[N];
int n;
double mp[100000];int m;
void iniMP(){
sort(mp+1,mp+1+m);
int p=0;
mp[++p]=mp[1];
for(int i=2;i<=m;i++) if(mp[i]!=mp[i-1]) mp[++p]=mp[i];
m=p;
}
Point a,b,c;
struct Interval{
double l,r;
bool operator <(const Interval &a) const{
return l==a.l?r<a.r:l<a.l;
}
Interval(double a=0,double b=0):l(a),r(b){}
}in[N];
double solve(double x){
int m=0;
for(int i=1;i<=n;i++){
a=t[i].a,b=t[i].b,c=t[i].c;
if(sgn(x-min(a.x,min(b.x,c.x)))<0||sgn(x-max(a.x,max(b.x,c.x)))>0 ) continue;
Line l1(a,b),l2(a,c),l3(b,c),l(Point(x,0),Point(x,1));
Point p[3];int cnt=0;
if(isLSI(l,l1)) p[++cnt]=LI(l,l1);
if(isLSI(l,l2)) p[++cnt]=LI(l,l2);
if(isLSI(l,l3)&&cnt!=2) p[++cnt]=LI(l,l3);
in[++m]=Interval(min(p[1].y,p[2].y),max(p[1].y,p[2].y));
}
sort(in+1,in+1+m);
double last=-INF,re=0;
for(int i=1;i<=m;i++){
if(in[i].l>last) re+=in[i].r-in[i].l,last=in[i].r;
else if(in[i].r>last) re+=in[i].r-last,last=in[i].r;
}
return re;
}
int main(int argc, const char * argv[]) {
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y);
t[i]=Triangle(a,b,c);
mp[++m]=a.x;mp[++m]=b.x;mp[++m]=c.x;
L[++nl]=Line(a,b,i);L[++nl]=Line(a,c,i);L[++nl]=Line(b,c,i);
}
for(int i=1;i<=n*3;i++)
for(int j=i+1;j<=n*3;j++)
if(L[i].id!=L[j].id&&sgn(Cross(L[i].t-L[i].s,L[j].t-L[j].s))!=0)
mp[++m]=LI(L[i],L[j]).x;
iniMP();
double ans=0;
for(int i=1;i<m;i++){
if(sgn(mp[i+1]-mp[i])>0){
double x=(mp[i]+mp[i+1])/2;
ans+=solve(x)*(mp[i+1]-mp[i]);
}
}
printf("%.2lf",ans-eps);
return 0;
}

面积并
https://wonderhoi.com/2024/09/06/面积并/
作者
wonderhoi
发布于
2024年9月6日
许可协议