Magic Line（牛客多校第三場）

Magic Line

本題大意：給出n個點，求出一條線，使之将所有的點分成數量相同的兩部分，線不能通過點。

首先我先把所有的點按照先橫坐标後縱坐标（都是由小到大），然後由于題目給的範圍很大，我們可以想到，如果取一條最為豎的線，那麼一定能分開，然後考慮一下最中間的兩個點橫坐标相同的情況即可。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <map>
#include <bitset>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#define ll long long
using namespace std;
#define maxn 1009
struct data
{
    int x,y;
} a[maxn];
bool cmp(data a1,data a2)
{
    if(a1.x==a2.x)return a1.y<a2.y;
    return a1.x<a2.x;
 
}
int main()
{
    int t;
    while(scanf("%d",&t)!=-1)
    {
        int y1=-999000000;
        int y2=999000000;
        while(t--)
        {
            int n;
            scanf("%d",&n);
            for(int i=1; i<=n; i++)scanf("%d%d",&a[i].x,&a[i].y);
            sort(a+1,a+1+n,cmp);
            int ans=n/2;
            if(a[ans].x==a[ans+1].x)//如果最中間的兩個點橫坐标相同，那就把線稍稍向向上平移一下
            {
                int x1=a[ans].x,x2=a[ans].x;
                x1--;
                x2++;
                int y3=a[ans].y;
                int y5=y3+999000001;
                int y6=y3-999000000;
                printf("%d %d %d %d\n",x1,y5,x2,y6);
            }
            else printf("%d %d %d %d\n",a[ans].x,y1,a[ans+1].x,y2);//不相同的話直接輸出
        }
    }
    return 0;
}