https://www.luogu.com.cn/problem/P1429
输入数据n在1e5,考虑1s算1e8次,然后我的第二个for循环开1e3就过了
1 #include<bits/stdc++.h> 2 #define max(a,b) a>b?a:b 3 #define min(a,b) a<b?a:b 4 using namespace std; 5 struct note 6 { 7 double x,y; 8 friend bool operator<(const note &qwq,const note &qaq) 9 { 10 return qwq.x<qaq.x; 11 } 12 }a[200005]; 13 int main() 14 { 15 register int i,j,n; 16 register double mn=1e20; 17 scanf("%d",&n); 18 int s=10000; 19 for(i=0;i<n;i++) 20 scanf("%lf%lf",&a[i].x,&a[i].y); 21 sort(a,a+n); 22 for(i=0;i<n;i++) 23 { 24 for(j=i+1;j<n&&j<i+s;j++) 25 mn=min(mn,(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)); 26 } 27 printf("%.4f",sqrt(mn)); 28 }
参考链接https://www.luogu.com.cn/blog/2-6-5-3-5/solution-p6247