141pts 求调
查看原帖
141pts 求调
837888
Fractured_Angel楼主2024/1/23 21:10

既有WA又有TLE,不知道为啥

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long LL;
inline int Read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9')
	{
		x = x * 10;
		x += ch - '0';
		ch = getchar();
	}
	return x * f;
}
const int MAXN = 1000005;
const LL INF = 1e17;
int n;
struct Point
{
	int x, y;
} P[MAXN], T[MAXN], Q[MAXN];
bool cmp(Point p, Point q)
{
	return p.x < q.x;
}
bool cmp2(Point p, Point q)
{
	return p.y < q.y;
}
LL dist(LL sx, LL sy, LL ex, LL ey)
{
	return (sx - ex) * (sx - ex) + (sy - ey) * (sy - ey);
}
LL Solve(int l, int r)
{
	if(l == r) return INF;
	int mid = (l + r) >> 1;
	LL d = min(Solve(l, mid), Solve(mid + 1, r));
	int ggg = P[mid].x;
	int i2 = l, j2 = mid + 1;
	int pos = l - 1;
	while(i2 <= mid || j2 <= r)
	{
		if(i2 > mid)
		{
			Q[++ pos] = P[j2];
			j2 ++;
			continue;
		}
		if(j2 > r)
		{
			Q[++ pos] = P[i2];
			i2 ++;
			continue;
		}
		if(P[i2].y <= P[j2].y)
		{
			Q[++ pos] = P[i2];
			i2 ++;
		}
		else
		{
			Q[++ pos] = P[j2];
			j2 ++;
		}
	}
	for(int i = l; i <= r; i ++) P[i] = Q[i];
	int tot = 0;
	for(int i = l; i <= r; i ++)
		if((P[i].x - ggg) * (P[i].x - ggg) < d) T[++ tot] = P[i];
	for(int i = 1; i <= tot; i ++)
		for(int j = i + 1; j <= tot && (T[j].y - T[i].y) * (T[j].y - T[i].y) < d; j ++)
			d = min(d, dist(T[i].x, T[i].y, T[j].x, T[j].y));
	return d;
}
int main()
{
	n = Read();
	for(LL i = 1; i <= n; i ++) 
	{
		P[i].x = Read(); 
		P[i].y = Read();
	}
	sort(P + 1, P + n + 1, cmp);
	printf("%lld\n", Solve(1, n));
	return 0;
}
2024/1/23 21:10
加载中...