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