Magic Line

解题思路

因为坐标的范围只有正负1000，且所有点坐标都是整数，所以所有点相连构成的最大斜率只有2000，而我们能够输出的的坐标范围是正负10^9。所以我们先把这n个点按照x轴从小到大，x相同的再按照y轴从大到小排序，然后取第n/2个点，在这个点上做一条斜率极大的线(大于2000即可)，此时在这条线的上方有n/2-1个点，下方有n/2个点，还有一个点在线上，我们先在线上取两个在图外的点(即x或y的绝对值大于1000)，然后把其中一个点的y坐标-1，此时两个点连接的线就相当于往下偏了一下，把原来线上的点放到了上面，又不会碰到下面的点。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N = 1005;

struct T{

    int x, y;

    T(){}

    T(int x, int y): x(x), y(y){}

    bool operator<(const T& a)const{

        if(x != a.x)

            return x < a.x;

        else

            return y > a.y;

    }

}e[N];

int main()

{

    int t;

    scanf("%d", &t);

    while(t --){

        int n;

        scanf("%d", &n);

        for(int i = 1; i <= n; i ++){

            int x, y;

            scanf("%d%d", &x, &y);

            e[i] = T(x, y);

        }

        sort(e + 1, e + n + 1);

        int x = e[n / 2].x, y = e[n / 2].y;

        ll k = 2001;

        ll b = y - k * x;

        printf("-2000 %lld 2000 %lld\n", -2000 * k + b, 2000 * k + b - 1);

    }

    return 0;

}

巴特西

2019牛客多校第三场H-Magic Line

Magic Line

解题思路

代码如下

最新文章

热门文章