【BZOJ 2402】陶陶的难题II

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2402

解题报告

不难发现这是一个分数规划问题
再化一化式子就可以转换成凸包上选点的问题
至于支持链上的询问我们可以套树链剖分
总的时间复杂度:$O(n \log^3 n)$

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;

int n, head[N], nxt[N], to[N];
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];

inline int read() {
	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;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

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() {
	n = read();
	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++) {
		AddEdge(read(), read());
	}
	HLD.init();
	for (int i = read(); i; i--) {
		printf("%.10lf\n", HLD.query(read(), read()));
	}
	return 0;
}

【BZOJ 4829】[HNOI2017] 队长快跑

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4829

解题报告

首先我们可以把每一条射线等价为一条垂直于$x$轴的射线
此时问题变成了$Flappy \ Bird$那样

然后我们发现问题就是上下两个凸包互相卡
然后用两个队列瞎搞搞就好了

另外这题精度巨坑
之前用$long double$各种判$EPS$还是挂成狗
所以建议安心用$long long$

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);

int n,tot,st[N],head[2],tail[2];
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];

inline int read() {
	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() {
	n = read(); tt.x = read(); tt.y = read();
	for (int i=1;i<=n;i++) {
		p[i].x = read(); p[i].y = read();
		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;
}

【模板库】二维凸包

参考例题:http://poj.org/problem?id=3348
备注:可以处理重点,坐标值可以是整数和小数

#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]; 

inline int read() {
	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() {
	n = read();
	for (int i=1;i<=n;i++) p[i].x = read(), p[i].y = read();
	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 3482】[COCI2013] hiperprostor

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3482
神犇题解:http://www.cnblogs.com/clrs97/p/4675155.html

解题报告

我们发现一条路径的长度为$ax+b$,是一条直线的形式
那么我们如果求出所有直线的凸包,那么就可以$O(n)$计算答案了

现在考虑如何搞出凸包:

若两条直线的斜率相等,那么纵截距较小的一定优于纵截距较大的
于是我们可以定义状态$f_{i,j}$表示到达$i$点,斜率为$j$,的路径纵截距最小是多少
这个我们可以使用Dijkstra搞出来,之后我们显然可以$O(n)$构造出凸包了

有了凸包后,每一条线段的贡献就是一个等差数列,这个显然可以$O(1)$计算
于是总的时间复杂度就是$O(Qn^2 \log (n^2))$

【BZOJ 4570】[SCOI2016] 妖怪

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4570

这个题,省选的时候思路一点没错啊!(╯‵□′)╯︵┻━┻
是我考试的时候心太急了,当然草稿纸太小绝对也是原因之一 (逃

就是推一推式子,发现是个凸包+对勾函数
于是搞一搞范围,求一求极值就可以辣!

#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;
 
inline int read(){
    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(){
    n = read();
    for (int i=1;i<=n;i++) p[i].x = read(), p[i].y = read();
    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;
}

【算法笔记】凸包上选点问题

问题一:在凸包上,选三个点使围成的面积最大
结论:一直不停的转一转,O(n)可过
证明:YYY的不严密的反证法

问题二:在凸包上,选四个点使围成的面积最大
结论:最优解一定是由两组对踵点对构成,于是旋转卡壳卡一卡也是O(n)的
证明:可以一步步证到,一般的点,一定不是最优解,进而证到,最优解一定是由两对对踵点对构成

哎,今晚好想睡觉,先简单写写,过几天再来填坑QAQ

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

题目传送门:http://pan.baidu.com/s/1nvKqStz
离线版题目:http://paste.ubuntu.com/18378190/
数据传送门:http://pan.baidu.com/s/1skSFZxr

哎呀,本来想着终于可以A题了!结果又被卡常QAQ,然后又只有60分QAQ
正解就是凸包+旋转卡壳+乱搞,然而原教的代码完全没有几何库,全部写进代码%%%%%%%,因此他天生自带小常数啊!
原教 Orz:http://paste.ubuntu.com/18378298/
哎呀,不想卡常了,贴一份代码水过就算了吧

#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;
}

唯一比较欣慰的,快4个月没有写过几何题了,居然还能写出来,还没怎么调试就过了。