UESTC 1170 红与蓝 计算几何、贪心、红蓝点对

UESTC 2016 Summer Training #16 Div.2

UESTC 1170

Source

贪心的做法

预处理所有Ai到O的距离， 然后根据距离排序，

之后依次对每个Bi也求出BiO， 然后二分查找， 然后处理最近的+-100个点， 答案必定在这100或者1000个点之内

比赛的时候是+-100 共200个点Accepted的

然后比赛结束后试了一下， 我这样的方法至少要+-40 共80个点才能通过那个题目的数据测试

好像还有专业计算几何的算法 红蓝点对 ☺☺

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;

struct p{
    int x, y;
    double dist;
} val[maxn];

inline bool cmp(const p& a, const p& b)
{
    return a.dist < b.dist;
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    int T = 2;
    while(T--){
    #endif // LOCAL

    int n, x, y, a, b;
    double dist, ans = maxn;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d%d", &val[i].x, &val[i].y);
        val[i].dist = sqrt(val[i].x*val[i].x + val[i].y*val[i].y);
    }
    sort(val, val + n, cmp);
    for(int i = 0; i < n; i++){
        scanf("%d%d", &x, &y);
        dist = sqrt(x*x + y*y);
        int m;
        a = 0, b = n - 1;
        while(a < b){ m = a + (b - a)/2; if(val[m].dist >= dist) b = m;
            else a  = m + 1;
        }
        for(int j = max(0, a - 100); j < min(n, a + 100); j++){
            ans = min(ans, sqrt((x - val[j].x)*(x - val[j].x) + (y - val[j].y)*(y - val[j].y)));
        }
    }
    printf("%.3f", ans);

    #ifdef LOCAL
    printf("n");
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx