## 【BZOJ 2402】陶陶的难题II

### Code

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

const int N = 60009;
const double INF = 1e9;
const double EPS = 1e-4;

struct Point{
double x, y;
inline Point() {
}
inline Point(double a, double b):x(a), y(b) {
}
inline bool operator < (const Point &PP) const {
return x < PP.x || (x == PP.x && y < PP.y);
}
inline bool operator == (const Point &PP) const {
return x == PP.x && y == PP.y;
}
inline Point operator - (const Point &PP) const {
return Point(x - PP.x, y - PP.y);
}
inline double operator * (const Point &PP) {
return x * PP.y - y * PP.x;
}
inline double slope() {
return y / x;
}
}d[N][2];

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 AddEdge(int u, int v) {
static int E = 1;
}

class HeavyLightDecomposition{
int fa[N], sz[N], dep[N], idx[N], hvy[N], top[N];
class SegmentTree{
vector<Point> cvx[N][2];
public:
int num[N], root, ch[N][2];
inline void init() {
build(root, 1, n);
}
inline void update(int l, int r, double a, double *mx) {
query(root, 1, n, l, r, a, mx);
}
private:
inline void query(int w, int l, int r, int L, int R, double a, double *mx) {
if (L <= l && r <= R) {
mx[0] = max(mx[0], cal(cvx[w][0], a));
mx[1] = max(mx[1], cal(cvx[w][1], a));
} else {
int mid = l + r + 1 >> 1;
if (L < mid) {
query(ch[w][0], l, mid - 1, L, R, a, mx);
}
if (R >= mid) {
query(ch[w][1], mid, r, L, R, a, mx);
}
}
}
inline double cal(const vector<Point> &que, double a) {
int l = 0, r = que.size() - 1, mid, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (mid == 0 || (que[mid] - que[mid - 1]).slope() >= a) {
ret = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return -a * que[ret].x + que[ret].y;
}
inline void build(int &w, int l, int r) {
static int cnt = 0;
w = ++cnt;
if (l == r) {
cvx[w][0].push_back(d[num[l]][0]);
cvx[w][1].push_back(d[num[l]][1]);
} else {
int mid = l + r + 1 >> 1;
build(ch[w][0], l, mid - 1);
build(ch[w][1], mid, r);
int ls = ch[w][0], rs = ch[w][1];
cvx[w][0] = Merge(cvx[ls][0], cvx[rs][0]);
cvx[w][1] = Merge(cvx[ls][1], cvx[rs][1]);
}
}
inline vector<Point> Merge(const vector<Point> &c1, const vector<Point> &c2) {
vector<Point> cur, ret;
for (int i = 0; i < (int)c1.size(); i++) {
cur.push_back(c1[i]);
}
for (int i = 0; i < (int)c2.size(); i++) {
cur.push_back(c2[i]);
}
sort(cur.begin(), cur.end());
cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
for (int i = 0; i < (int)cur.size(); i++) {
while ((int)ret.size() > 1) {
int idx = ret.size() - 1;
if ((cur[i] - ret[idx - 1]) * (ret[idx] - ret[idx - 1]) <= EPS) {
ret.pop_back();
} else {
break;
}
}
ret.push_back(cur[i]);
}
return ret;
}
}SGT;
public:
inline void init() {
DFS1(1, 1);
DFS2(1, 1);
SGT.init();
}
inline double query(int u, int v) {
double l = 0, r = INF, ret = 0, mid;
while (r - l > EPS) {
mid = (l + r) * 0.5;
if (judge(u, v, mid)) {
ret = mid;
l = mid;
} else {
r = mid;
}
}
return ret;
}
private:
inline bool judge(int u, int v, double a) {
double mx[] = {-INF, -INF};
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
SGT.update(idx[top[u]], idx[u], a, mx);
u = fa[top[u]];
} else {
SGT.update(idx[top[v]], idx[v], a, mx);
v = fa[top[v]];
}
}
if (dep[u] > dep[v]) {
SGT.update(idx[v], idx[u], a, mx);
} else {
SGT.update(idx[u], idx[v], a, mx);
}
return mx[0] + mx[1] > 0;
}
inline void DFS1(int w, int f) {
fa[w] = f;
sz[w] = 1;
dep[w] = dep[f] + 1;
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] != f) {
DFS1(to[i], w);
sz[w] += sz[to[i]];
if (sz[to[i]] > sz[hvy[w]]) {
hvy[w] = to[i];
}
}
}
}
inline void DFS2(int w, int t) {
static int dcnt = 0;
SGT.num[idx[w] = ++dcnt] = w;
top[w] = t;
if (hvy[w]) {
DFS2(hvy[w], t);
}
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] != fa[w] && to[i] != hvy[w]) {
DFS2(to[i], to[i]);
}
}
}
}HLD;

int main() {
for (int i = 1; i <= n; i++) {
scanf("%lf", &d[i][0].x);
}
for (int i = 1; i <= n; i++) {
scanf("%lf", &d[i][0].y);
}
for (int i = 1; i <= n; i++) {
scanf("%lf", &d[i][1].x);
}
for (int i = 1; i <= n; i++) {
scanf("%lf", &d[i][1].y);
}
for (int i = 1; i < n; i++) {
}
HLD.init();
for (int i = read(); i; i--) {
}
return 0;
}


## 【BZOJ 4829】[HNOI2017] 队长快跑

### Code

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

const int N = 1000009;
const int LEN = 1e4;
const double PI = acos(-1);

struct Point{
LL x,y; Point *nxt; int pt;
inline Point() {}
inline Point(LL a, LL b):x(a),y(b) {}
inline Point operator + (const Point &P) {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 t) {return Point(x * t, y * t);}
inline LL operator ^ (const Point &P) {return x * P.x + y * P.y;}
inline LL operator * (const Point &P) {return x * P.y - y * P.x;}
inline bool operator < (const Point &P) const {return x < P.x;}
inline bool operator != (const Point &P) const {return x != P.x || y != P.y;}
inline double len() {return sqrt(x * x + y * y);}
}ss,tt,p[N],vout[N],*que[2][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 bool NotInRange(double div, double a, double b) {
if (div >= -PI / 2 && div <= PI / 2) return (a < div || a > PI / 2) && (b < div || b > PI / 2);
else if (div < 0) return a > div && a < PI / 2 && b > div && b < PI / 2;
else return (a > div || a < PI / 2) && (b > div || b < PI / 2);
}

int main() {
for (int i=1;i<=n;i++) {
double r1,r2,r3; scanf("%lf",&r1);
r2 = atan2((ss-p[i]).y, (ss-p[i]).x);
r3 = atan2((tt-p[i]).y, (tt-p[i]).x);
if (NotInRange(r1, r2, r3)) p[i].pt = 1; //射线朝上
else p[i].pt = 0; //射线朝下
}
sort(p+1, p+1+n);
int lim = n; n = 0;
for (int i=1;i<=lim;i++) {
if (p[i].x < ss.x || tt.x < p[i].x) continue;
p[++n] = p[i];
}
p[++n] = tt;
que[0][tail[0] = head[0] = 1] = &ss;
que[1][tail[1] = head[1] = 1] = &ss;
for (int i=1;i<=n;i++) {
int &h1 = head[p[i].pt], &h2 = head[p[i].pt ^ 1], &t1 = tail[p[i].pt], &t2 = tail[p[i].pt ^ 1];
Point **a1 = que[p[i].pt], **a2 = que[p[i].pt ^ 1];
if (h2 < t2 && ((p[i] - *a2[h2]) * (*a2[h2 + 1] - *a2[h2])) * (p[i].pt==1? 1: -1) >= 0) {
while (h2 < t2 && ((p[i] - *a2[h2]) * (*a2[h2 + 1] - *a2[h2])) * (p[i].pt==1? 1: -1) >= 0) {
++h2;
}
p[i].nxt = a2[h2];
a1[h1 = t1 = t1 + 1] = a2[h2];
} else {
while (h1 < t1 && ((p[i] - *a1[t1 - 1]) * (*a1[t1] - *a1[t1 - 1])) * (p[i].pt==1? 1: -1) >= 0) {
--t1;
}
p[i].nxt = a1[t1];
}
a1[++t1] = &p[i];
}
double ans = 0;
for (Point *cur=&p[n],*last;*cur!=ss;) {
last = cur; cur = cur->nxt;
ans += (*cur - *last).len();
}
printf("%.10lf\n",ans);
return 0;
}


## 【模板库】二维凸包

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;

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

int n,cnt;

struct Point{
double x,y;
inline Point() {}
inline Point(double a, double b):x(a),y(b) {}
inline Point operator + (const Point &A) {return Point(x+A.x, y+A.y);}
inline Point operator - (const Point &A) {return Point(x-A.x, y-A.y);}
inline Point operator / (double A) {return Point(x/A, y/A);}
inline Point operator * (double A) {return Point(x*A, y*A);}
inline double operator * (const Point &A) {return x*A.x + y*A.y;}
inline double operator ^ (const Point &A) {return x*A.y - A.x*y;}
inline bool operator < (const Point &B) const {return x < B.x - EPS || (fabs(x-B.x) < EPS && y < B.y - EPS);}
inline bool operator == (const Point &B) const {return fabs(x - B.x) + fabs(y - B.y) < EPS;}
}p[N],cvx[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 ConvexHull(int tot, Point *a, int &sz, Point *ret) {
if (!tot) {sz = 0; return;}
sort(a+1, a+1+tot); ret[sz=1] = a[1];
tot = unique(a+1, a+1+tot) - a - 1;
for (int i=2;i<=tot;i++) {
while (sz > 1 && ((ret[sz] - ret[sz-1]) ^ (a[i] - ret[sz])) < EPS) sz--;
ret[++sz] = a[i];
}
for (int i=tot-1,mn=sz;i>0;i--) {
while (sz > mn && ((ret[sz] - ret[sz-1]) ^ (a[i] - ret[sz])) < EPS) sz--;
ret[++sz] = a[i];
}
sz -= sz > 2;
}

int main() {
ConvexHull(n, p, cnt, cvx);
double vout = 0;
for (int i=2;i<cnt;i++)
vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]) / 2;
printf("%d\n",(int)(vout/50));
return 0;
}


## 【BZOJ 4570】[SCOI2016] 妖怪

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

const int N = 1000000+9;
const double INF = 1e100;

struct Point{
#define Vector Point
int x,y;
inline Point() {}
inline Point(int _x, int _y):x(_x),y(_y){}
inline bool operator < (const Point &B) const{return (x<B.x)||(x==B.x&&y<B.y);}
inline Point operator - (const Point &B) {Point C; C.x=x-B.x; C.y=y-B.y; return C;}
inline LL operator * (const Point &B) {return (LL)x*B.y - (LL)y*B.x;}
}p[N],con[N];
int n,cnt;
double vout = INF;

char c=getchar(); int ret=0,f=1;
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 ConvexHull(){
con[++cnt] = p[n];
for (int i=n-1;i;i--) {
while (cnt > 1 && (con[cnt]-con[cnt-1])*(p[i]-con[cnt-1]) <= 0LL) cnt--;
con[++cnt] = p[i];
}
while (cnt > 1 && con[cnt].y <= con[cnt-1].y) cnt--;
}

int main(){
sort(p+1,p+1+n); ConvexHull(); double R, L=INF, MN;
for (int i=1;i<=cnt;i++) {
Vector v = con[i+1] - con[i];
swap(L, R); L = i!=cnt?(double)-v.y / v.x:0;
MN = sqrt((double)con[i].y / con[i].x);
if (R < MN) vout = min(vout, con[i].x*R + con[i].y/R + con[i].x + con[i].y);
else if (L > MN) vout = min(vout, con[i].x*L + con[i].y/L + con[i].x + con[i].y);
else vout = min(vout, con[i].x*MN + con[i].y/MN + con[i].x + con[i].y);
} printf("%.4lf\n",vout);
return 0;
}


## 【NOI六连测】[D3T2] 最大土地面积

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;

const int MAXN = 8000+9;
const double EPS = 1e-8;
const double INF = 1e30;

double vout;
int n;

inline int cmp(double x){if (fabs(x)<EPS) return 0; else return (x>0)?1:-1;}

struct Point{
double x,y;
inline bool operator < (const Point &A) const {return (x < A.x) || (x == A.x && y < A.y);} inline bool operator == (const Point &A) const {return !cmp(x-A.x) && !cmp(y-A.y);} inline Point operator + (const Point &A) {Point tmp;tmp.x=x+A.x;tmp.y=y+A.y;return tmp;} inline Point operator - (const Point &A) {Point tmp;tmp.x=x-A.x;tmp.y=y-A.y;return tmp;} }p[MAXN],TMP[MAXN],ori[MAXN],SIZE[MAXN]; typedef Point Vector; inline double Cross(Vector A, Vector B){return A.x*B.y - A.y*B.x;} inline double Area2(Point A, Point B, Point C){return Cross(B-A, C-A);} inline bool Onleft(Point A, Point B, Point C){return cmp(Area2(A,B,C)) > 0;}

inline void CalArea(Point *A){
A[5] = A[1]; double ret = 0;
for (int i=1;i<=4;i++)
ret += Cross(A[i],A[i+1]);
vout = max(vout, fabs(ret));
}

inline int ConvexHull(Point *A, int N){
sort(A+1,A+1+N); int cnt=0;

for (int i=1;i<=N;i++){ while (cnt > 1 && !Onleft(TMP[cnt-1],TMP[cnt],A[i])) cnt--;
TMP[++cnt] = A[i];
} for (int i=N-1,lim=cnt;i;i--){
while (cnt > lim && !Onleft(TMP[cnt-1],TMP[cnt],A[i])) cnt--;
TMP[++cnt] = A[i];
}

if (cnt==4 && N==4) {
for (int i=1,tag;i<=4;i++){
tag = 0;
for (int j=1;j<cnt;j++)
if (A[i] == TMP[j]) tag = 1;
if (!tag) {A[4]=A[i];break;}
}
} for (int i=1;i<cnt;i++) A[i] = TMP[i];
return cnt-1;
}

inline void update(Point *A){
if (ConvexHull(A,4) == 4) CalArea(A);
else {
double sa = fabs(Area2(A[1],A[2],A[3]));
double mn = INF; A[5] = A[4]; A[4] = A[1];
for (int i=1;i<=3;i++) mn = min(mn, fabs(Area2(A[i],A[i+1],A[5])));
if (vout < sa-mn) vout = max(vout, sa-mn);
}
}

inline void cycle(int N){
for (int i=1;i<=N;i++) p[i+N] = p[i];
for (int i=1;i<=N;i++) p[i+N*2] = p[i];
for (int k=2;k<N;k++){
for (int i=1,itr1=2,itr2=i+k+1;i<=N;i++){
while (itr1 < i+k && fabs(Area2(p[i],p[itr1],p[i+k])) <= fabs(Area2(p[i],p[itr1+1],p[i+k]))) itr1++;
while (itr2 < i+N && fabs(Area2(p[i+k],p[itr2],p[i])) <= fabs(Area2(p[i+k],p[itr2+1],p[i]))) itr2++;
SIZE[1] = p[i]; SIZE[2] = p[itr1]; SIZE[3] = p[i+k]; SIZE[4] = p[itr2];
CalArea(SIZE);
}
}
}

int main(){
freopen("large.in","r",stdin);
freopen("large.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y),
ori[i] = p[i];
int tmp = ConvexHull(p,n);
if (tmp == 4) CalArea(p);
else if (tmp == 3) for (int i=1;i<=n;i++){
int t = 1;
for (int j=1;j<=3;j++)
if (p[j]==ori[i]) t=0;
if (t) p[4] = ori[i], update(p);
} else cycle(tmp);
printf("%.3lf",vout/2.0);
return 0;
}