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

Re:请不要想复杂了,对付最近点对最好的办法永远是旋转坐标系+O(n^2)暴力

Posted by pwfange at 2021-11-08 20:30:22 on Problem 3714
In Reply To:请不要想复杂了,对付最近点对最好的办法永远是旋转坐标系+O(n^2)暴力 Posted by:KomejiSylfii at 2014-06-06 11:03:48
> 附赠代码
> #include <cmath>
> #include <cstdio>
> #include <cstring>
> #include <algorithm>
> using namespace std;
> 
> int T;
> 
> const double ran = 115.15215;
> 
> struct vec { double x, y; } ;
> 
> vec operator - (vec a, vec b) { return (vec) { a.x - b.x, a.y - b.y } ; }
> 
> double dis(vec a) { return sqrt(a.x * a.x + a.y * a.y); }
> 
> vec rota(vec a, double b)
> { return (vec) { cos(b) * a.x - sin(b) * a.y, sin(b) * a.x + cos(b) * a.y }; }
> 
> bool cmp(const vec &a, const vec &b)
> { return a.x == b.x ? a.y < b.y : a.x < b.x; }
> 
> vec a[100010];
> vec b[100010];
> 
> int n;
> 
> int main()
> {
>     freopen("3714.in", "r", stdin);
>     freopen("3714.out", "w", stdout);
> 
>     scanf("%d", &T);
>     while (T--)
>     {
> 	double ans = 1e11;
> 	scanf("%d", &n);
> 	for (int i = 1; i <= n; ++i)
> 	{
> 	    scanf("%lf%lf", &a[i].x, &a[i].y);
> 	    rota(a[i], ran);
> 	}
> 	for (int i = 1; i <= n; ++i)
> 	{
> 	    scanf("%lf%lf", &b[i].x, &b[i].y);
> 	    rota(b[i], ran);
> 	}
> 	
> 	sort(a + 1, a + n + 1, cmp);
> 	sort(b + 1, b + n + 1, cmp);
> 
> 	int t = 1;
> 	for (int i = 1; i <= n; ++i)
> 	{
> 	    while (t < n && cmp(a[t + 1], b[i])) ++t;
> 	    for (int j = t; j <= n; ++j)
> 	    {
> 		if (fabs(a[j].x - b[i].x) > ans) break;
> 		ans = min(ans, dis(a[j] - b[i]));
> 	    }
> 	    for (int j = t - 1; j; --j)
> 	    {
> 		if (fabs(a[j].x - b[i].x) > ans) break;
> 		ans = min(ans, dis(a[j] - b[i]));
> 	    }
> 	}
> 	printf("%.3f\n", ans);
>     }
>     return 0;
> }
> 	
>     
> 

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