分治

分治做法还不会,以后再补、、、
https://www.luogu.com.cn/problem/P1257
https://www.luogu.com.cn/problem/P1429
https://www.luogu.com.cn/problem/P7883
//随机坐标旋转一定角度,然后按照x或y进行排序,从前往后找k个点即可,k == 5的时候就ac了。。。。。。
//旋转角度公式:  //x'=xcosθ-ysinθ
				//y'=xsinθ+ycosθ
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e6+9;

struct Point {
    long double x,y;
}Points[N];

bool operator < (Point a,Point b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

long double get_dis(int p,int q) {
    long double dx = Points[p].x - Points[q].x;
    long double dy = Points[p].y - Points[q].y;
    return sqrtl(dx * dx + dy * dy);
}

int main() {
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) {
        long double x,y,x_,y_;
        scanf("%LF%LF",&x,&y);
        x_ = x,y_ = y;
        x = x_ * cosl(1) - y_ * sinl(1),y = x_ * sinl(1) + y_ * cosl(1);
        Points[i] = {x,y};
    }
    sort(Points+1,Points+n+1);
    long double ans = 2e18;
    for(int i=1; i<=n; i++) {
        for(int j=i+1; j<=n && j <= i+5; j++) {
            ans = min(ans,get_dis(i,j));
        }
    }
    printf("%.4LF\n",ans);
    return 0;
}

全部评论

相关推荐

05-29 22:11
门头沟学院 Java
Elastic90:抛开学历造假不谈,这公司的招聘需求也挺怪的,Java开发还要求你有图文识别、移动端开发和c++的经验,有点逆天了。
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 10:39
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务