Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么这题在求最远点对的时候用旋转卡壳不对?

Posted by johann at 2016-07-09 22:54:22 on Problem 3384
是不是我的旋转卡壳写错了?
void RC(int n, Poi* p) {
	sort(p, p + n);
	double mx = -inf; Poi p1, p2;
	p[n] = p[0];
	for(int u = 0, v = 1; u < n; u++) {
		for(;;) {
			double tmp = cross(p[u + 1] - p[u], p[v + 1] - p[v]);
			if (dcmp(tmp) <= 0) {
				double dis = dist(p[u], p[v]);
				if (dis > mx) mx = dis, p1 = p[u], p2 = p[v];
				dis = dist(p[u], p[v + 1]);
				if (dis > mx) mx = dis, p1 = p[u], p2 = p[v + 1]; 
				break;
			}
			v = (v + 1) % n;
		}
	}
	printf("%.4lf %.4lf %.4lf %.4lf\n", p1.x, p1.y, p2.x, p2.y);
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator