| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为什么这题在求最远点对的时候用旋转卡壳不对?是不是我的旋转卡壳写错了?
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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator