萌新袜子刚学OI代码90pts TLE求条
查看原帖
萌新袜子刚学OI代码90pts TLE求条
746761
zzb1217楼主2024/11/19 21:04

rt,TLE最后一个点

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
struct dot {
	int x, y;
}a[N], x[N];
int n;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}

inline double dis(dot a, dot b) {
	return 1ll * sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
inline double dfs(int l, int r) {
	if (l >= r) return 1e18;
	int mid = (l + r) >> 1;
	double ans = min(dfs(l, mid), dfs(mid + 1, r));
	register int top = 0;
	for (register int i = l; i <= r; ++i) {
		if (abs(a[i].x - a[mid].x) > ans) continue;
		x[++top] = a[i];
	}
	sort(x + 1, x + top + 1, [&](dot a, dot b){return a.y < b.y;});
	for (register int i = 1; i <= top; ++i) {
		for (register int j = i + 1; j <= top; ++j) {
			for (register int k = j + 1; k <= top; ++k) {
				if (abs(x[j].y - x[i].y) + abs(x[i].y - x[k].y) + abs(x[j].y - x[k].y) >= ans) break;
				ans = min(ans, dis(x[i], x[j]) + dis(x[i], x[k]) + dis(x[j], x[k]));
			}	
		}  
	}
	return ans;
}
signed main(){
	n = read();
	for (int i = 1; i <= n; ++i) {
		a[i].x = read();
		a[i].y = read(); 
	}
	sort(a + 1, a + n + 1, [&](dot a, dot b){return a.x < b.x;});
	double w = dfs(1, n);
	printf("%.6lf", w);
}
2024/11/19 21:04
加载中...