## 【BZOJ 1137】[POI2009] Wsp 岛屿

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const double EPS = 1e-6;

int n, m, tot;
vector<int> del[N];
struct Point{
double x, y;
inline Point() {
}
inline Point(double _x, double _y):x(_x), y(_y) {
}
inline Point operator - (const Point &P) const {
return Point(x - P.x, y - P.y);
}
inline Point operator + (const Point &P) {
return Point(x + P.x, y + P.y);
}
inline Point operator * (double d) {
return Point(x * d, y * d);
}
inline double operator * (const Point &P) {
return x * P.y - y * P.x;
}
inline double len() {
return sqrt(x * x + y * y);
}
}p[N];
struct Line{
Point a, b;
double slope;
inline Line() {
}
inline Line(const Point &_a, const Point &_b):a(_a), b(_b) {
}
inline bool operator < (const Line &L) const {
return slope < L.slope;
}
inline Point intersect(const Line &L) {
double s1 = (L.b - L.a) * (b - L.a);
double s2 = (a - L.a) * (L.b - L.a);
return a + (b - a) * (s2 / (s1 + s2));
}
inline bool OnLeft(const Point &P) {
return (b - a) * (P - a) > EPS;
}
}l[N];

char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline void HalfPlaneIntersection(Line *arr, int &sz) {
for (int i = 1; i <= sz; i++) {
Point vec = arr[i].b - arr[i].a;
arr[i].slope = atan2(vec.y, vec.x);
}
sort(arr + 1, arr + 1 + sz);
int l = 1, r = 0;
for (int i = 1; i <= sz; i++) {
for (; l < r && !arr[i].OnLeft(arr[r].intersect(arr[r - 1])); r--);
for (; l < r && !arr[i].OnLeft(arr[l].intersect(arr[l + 1])); l++);
arr[++r] = arr[i];
}
for (; l < r - 1 && !arr[l].OnLeft(arr[r].intersect(arr[r - 1])); r--);
sz = 0;
for (int i = l; i <= r; i++) {
arr[++sz] = arr[i];
}
arr[0] = arr[sz];
arr[sz + 1] = arr[1];
}

int main() {
for (int i = 1; i <= n; i++) {
}
for (int i = 1; i <= m; i++) {
del[min(x, y)].push_back(max(x, y));
}
for (int i = 1; i < n; i++) {
sort(del[i].begin(), del[i].end());
int to = n;
while (!del[i].empty() && *--del[i].end() == to) {
to--;
del[i].pop_back();
}
if (i == 1 && to == n) {
printf("%.10lf", (p[1] - p[n]).len());
exit(0);
}
if (to > i) {
l[++tot] = Line(p[to], p[i]);
}
}
l[++tot] = Line(p[1], p[n]);
HalfPlaneIntersection(l, tot);
double ans = -(p[1] - p[n]).len();
Point last = l[1].intersect(l[0]);
for (int i = 1; i <= tot; i++) {
Point cur = l[i].intersect(l[i + 1]);
ans += (cur - last).len();
last = cur;
}
printf("%.10lf\n", ans);
return 0;
}


## 【模板库】半平面交

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;
const double EPS = 1e-8;

int n,m;

struct Point{
double x,y;
inline Point() {}
inline Point(double a, double b):x(a),y(b) {}
inline Point operator + (const Point &P) const {return Point(x+P.x, y+P.y);}
inline Point operator - (const Point &P) const {return Point(x-P.x, y-P.y);}
inline Point operator * (double d) const {return Point(x*d, y*d);}
inline Point operator / (double d) const {return Point(x/d, y/d);}
inline double operator * (const Point &P) const {return x*P.x + y*P.y;}
inline double operator ^ (const Point &P) const {return x*P.y - P.x*y;}
}p[N],cvx[N];

struct Line{
Point a,b; double slp;
inline Line() {}
inline Line(const Point &x, const Point &y) {a = x; b = y; slp = atan2(b.y-a.y, b.x-a.x);}
inline bool operator < (const Line &L) const {return slp < L.slp - EPS || (fabs(slp-L.slp) < EPS && ((b-a)^(L.b-a)) < -EPS);}
inline bool operator != (const Line &L) {return fabs(slp - L.slp) > EPS;}
inline bool onleft(const Point &P) {return ((b - a) ^ (P - a)) > EPS;}
inline double len() {return sqrt((b - a) * (b - a));}
inline Point ins(const Line &L) {
double s1 = (b - L.b) ^ (L.a - L.b);
double s2 = (a - L.a) ^ (L.b - L.a);
Point tmp = a + (((b - a) * s2) / (s1 + s2));
return a + (((b - a) * s2) / (s1 + s2));
}
}l[N],que[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void HalfPlaneIntersection(int tot, Line *a, int &cnt, Line *b, Point *c) {
sort(a+1, a+1+tot); cnt = tot; tot = 1;
for (int i=2;i<=cnt;i++) if (a[i] != a[i-1]) a[++tot] = a[i];
b[1] = a[1]; b[2] = a[2]; int l=1,r=2;
for (int i=3;i<=tot;i++) {
while (l < r && !a[i].onleft(b[r-1].ins(b[r]))) r--;
while (l < r && !a[i].onleft(b[l].ins(b[l+1]))) l++;
b[++r] = a[i];
}
while (l < r && !b[l].onleft(b[r].ins(b[r-1]))) r--;
while (l < r && !b[r].onleft(b[l].ins(b[l+1]))) l++;
cnt = 0; b[0] = b[r];
for (int i=l;i<=r;i++) b[++cnt] = b[i];
for (int i=1;i<=cnt;i++) c[i] = b[i].ins(b[i-1]);
}

int main() {
for (int i=1;i<=n;i++) {
p[m+1] = p[1];
for (int j=1;j<=m;j++) l[++tot] = Line(p[j], p[j+1]);
}
HalfPlaneIntersection(tot, l, cnt, que, cvx);
double vout = 0;
for (int i=2;i<cnt;i++) vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]);
printf("%.3lf\n",vout/2);
return 0;
}


## 【BZOJ 2618】[CQOI2006] 凸多边形

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;
const double EPS = 1e-8;

int n,m;

struct Point{
double x,y;
inline Point() {}
inline Point(double a, double b):x(a),y(b) {}
inline Point operator + (const Point &P) const {return Point(x+P.x, y+P.y);}
inline Point operator - (const Point &P) const {return Point(x-P.x, y-P.y);}
inline Point operator * (double d) const {return Point(x*d, y*d);}
inline Point operator / (double d) const {return Point(x/d, y/d);}
inline double operator * (const Point &P) const {return x*P.x + y*P.y;}
inline double operator ^ (const Point &P) const {return x*P.y - P.x*y;}
}p[N],cvx[N];

struct Line{
Point a,b; double slp;
inline Line() {}
inline Line(const Point &x, const Point &y) {a = x; b = y; slp = atan2(b.y-a.y, b.x-a.x);}
inline bool operator < (const Line &L) const {return slp < L.slp - EPS || (fabs(slp-L.slp) < EPS && ((b-a)^(L.b-a)) < -EPS);}
inline bool operator != (const Line &L) {return fabs(slp - L.slp) > EPS;}
inline bool onleft(const Point &P) {return ((b - a) ^ (P - a)) > EPS;}
inline double len() {return sqrt((b - a) * (b - a));}
inline Point ins(const Line &L) {
double s1 = (b - L.b) ^ (L.a - L.b);
double s2 = (a - L.a) ^ (L.b - L.a);
return a + (((b - a) * s2) / (s1 + s2));
}
}l[N],que[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void HalfPlaneIntersection(int tot, Line *a, int &cnt, Line *b, Point *c) {
sort(a+1, a+1+tot); cnt = tot; tot = 1;
for (int i=2;i<=cnt;i++) if (a[i] != a[i-1]) a[++tot] = a[i];
b[1] = a[1]; b[2] = a[2]; int l=1,r=2;
for (int i=3;i<=tot;i++) {
while (l < r && !a[i].onleft(b[r-1].ins(b[r]))) r--;
while (l < r && !a[i].onleft(b[l].ins(b[l+1]))) l++;
b[++r] = a[i];
}
while (l < r && !b[l].onleft(b[r].ins(b[r-1]))) r--;
while (l < r && !b[r].onleft(b[l].ins(b[l+1]))) l++;
cnt = 0; b[0] = b[r];
for (int i=l;i<=r;i++) b[++cnt] = b[i];
for (int i=1;i<=cnt;i++) c[i] = b[i].ins(b[i-1]);
}

int main() {
for (int i=1;i<=n;i++) {
p[m+1] = p[1];
for (int j=1;j<=m;j++) l[++tot] = Line(p[j], p[j+1]);
}
HalfPlaneIntersection(tot, l, cnt, que, cvx);
double vout = 0;
for (int i=2;i<cnt;i++) vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]);
printf("%.3lf\n",vout/2);
return 0;
}