隐藏
「WC2010」能量场 - 凸包+旋转卡壳/三分 | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

「WC2010」能量场 - 凸包+旋转卡壳/三分

发表于 更新于 分类于 Valine：

题目大意

    物理学家栋栋最近在研究一个能量场。在这个能量场中有$n$个粒子,每个粒子都有两个属性:质量$m$和结合系数$c$。
    栋栋发现,在这个能量场中,每个粒子都有两极,$N$极和$S$极。两个粒子相遇时,符合“同极相斥,异极相吸”的原则,只能是一个粒子的$N$极和另一个粒子的$S$极连接到一起。当质量为$m_a$,结合系数为$c_a$的粒子$a$的$N$极与另一个质量为$m_b$,结合系数为$c_b$的粒子$b$的$S$极直接连接时,可以产生大小为

    的结合能量。
    请解决以下两个问题:
    1.在能量场的$n$个粒子中哪两个粒子直接连接的能量最大。
    2.栋栋发明了一种方法,能选择其中的任意$k$个粒子$p_1,p_2,\ldots,p_k$,将$p_i$的$N$极与$p_i+1$的$S$极连接$(1\le i\lt k)$,$p_k$的$N$极与$p_1$的$S$极连接, 即连接能一个环,其中$p_1,p_2,\ldots,p_k$两两不同,$k$可以在$1$至$n$中任意取值。由于栋栋的技术有限,连接的时候产生负能量的那些连接在环中必须是连续的。如使用栋栋的这种方法连接,选择哪些粒子可以得到最大的能量。

题目分析

将题目给出的式子拆开：

令$x_a=m_ac_a,y_a=m_a$，故$m_am_b(c_a-c_b)=x_ay_b-x_by_a$。
这是一个叉积形式，最大值一定在凸包上。
故第一问求出凸包加上旋转卡壳即可。
三分也是可以的。
至于为什么可以用旋转卡壳，因为是双峰函数，因此找到一个最优解另一个一定能够旋转得到（但本人这样写没有过，改成两次卡壳才过，因此存疑求解答）。

就算没有看出叉积形式，写出cdq斜率优化的式子考虑精度问题后也能想到吧。。。

不难发现第二问求的是简单多边形面积，因此直接输出凸包即可。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=50005;
const double eps=1e-12;

int dcmp(double x) {
	if(fabs(x)<=eps)return 0;
	return x>eps?1:-1;
}

struct Point {
	double x,y;
	int id;
	Point(double _x=0,double _y=0,int _id=0):x(_x),y(_y),id(_id) {}
	Point operator - (const Point& b) const {
		return Point(b.x-x,b.y-y);
	}
	bool operator < (const Point& b) const {
		return x<b.x||(x==b.x&&y<b.y);
	}
} p[maxn];

typedef Point Vector;

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

int ConvexHull(int n,Point* p,Point* ans) { //此处存疑
	sort(p+1,p+n+1);
	int top=0;
	for(int i=1; i<=n; i++) { //下凸包
		while(top>1&&dcmp(Cross(ans[top-1]-p[i],ans[top-1]-ans[top]))>=0)top--;
		ans[++top]=p[i];
	}
	int k=top;
	for(int i=n-1; i>=1; i--) { //上凸包
		while(top>k&&dcmp(Cross(ans[top-1]-p[i],ans[top-1]-ans[top]))>=0)top--;
		ans[++top]=p[i];
	}
	if(n>1)top--;
	return top;
}

int ansa,ansb;

double Rotating_Calipers(int n,Point* p) {
	double ans=0;
	p[n+1]=p[1];
	int b=1;
	for(int a=1; a<=n; a++) {
		while(dcmp(fabs(Cross(p[a],p[b+1]))-fabs(Cross(p[a],p[b])))>=0)b=b%n+1;
		if(dcmp(fabs(Cross(p[a],p[b]))-ans)>0) {
			ans=fabs(Cross(p[a],p[b]));
			int tmpa=a,tmpb=b;
			if(Cross(p[a],p[b])<0)swap(tmpa,tmpb);
			ansa=p[tmpa].id;
			ansb=p[tmpb].id;
		}
	}
	b=n;
	p[0]=p[n];
	for(int a=n; a>=1; a--) {
		while(dcmp(fabs(Cross(p[a],p[b-1]))-fabs(Cross(p[a],p[b])))>=0)b=b==1?n:b-1;
		if(dcmp(fabs(Cross(p[a],p[b]))-ans)>0) {
			ans=fabs(Cross(p[a],p[b]));
			int tmpa=a,tmpb=b;
			if(Cross(p[a],p[b])<0)swap(tmpa,tmpb);
			ansa=p[tmpa].id;
			ansb=p[tmpb].id;
		}
	}
	return ans;
}

int n;
Point ans[maxn];

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++) {
		double m,c;
		scanf("%lf%lf",&m,&c);
		p[i]=Point(m*c,m,i);
	}
	int tot=ConvexHull(n,p,ans);
	Rotating_Calipers(tot,ans);
	printf("%d %d\n",ansa,ansb);
	printf("%d\n",tot);
	for(int i=1; i<=tot; i++)printf("%d ",ans[i].id);
	return 0;
}
相关文章
姥爷们赏瓶冰阔落吧~