2019牛客暑期多校训练营(第三场)- H Magic Line (计算几何)

题目链接:https://ac.nowcoder.com/acm/contest/883/H

题意:给定n个点(n为偶数),求一条直线使得n个点平均分散在直线两端,即每端n/2个点。

思路:把n个点按x升序排列,x相等时按y升序排列,这时候我们取第n/2个点和第n/2+1个点,以它两为界限,把n个点均分。因为n个点的坐标<=1e3,而我们的直线的点可以<=1e9,那么一定可以找到一条很陡的直线满足条件。

2019牛客暑期多校训练营(第三场)- H Magic Line (计算几何)

图片来自:https://www.cnblogs.com/st1vdy/p/11245932.html

AC代码:

#include<cstdio>
#include<algorithm>
using namespace std;

int T,n;

struct node{
    int x,y;
}pt[1005];

bool cmp(node a,node b){
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            scanf("%d%d",&pt[i].x,&pt[i].y);
        sort(pt+1,pt+n+1,cmp);
        int x1=pt[n/2].x,y1=pt[n/2].y;
        int x2=pt[n/2+1].x,y2=pt[n/2+1].y;
        int xx1,xx2,yy1,yy2;
        if((y1+y2)>=0)
            yy1=1e9,yy2=y1-(yy1-y2);
        else
            yy2=-1*1e9,yy1=y2+(y1-yy2);
        if((x1+x2)%2==0)
            xx1=(x1+x2)/2-1,xx2=xx1+2;
        else
            xx1=x1+(x2-x1)/2,xx2=xx1+1;
        printf("%d %d %d %d\n",xx1,yy1,xx2,yy2);
    }
    return 0;
}

 

上一篇:1037 Magic Coupon (25 分)题解 updating


下一篇:find与grep