大致题意:
输入测试用例个数T,输入点的个数n(n为偶数),再分别输入n个不同的点的坐标,要求输出四个整数x1,y1,x2,y2,表示有一条经过点(x1,y1),(x2,y2)的直线将该二维平面内的点分成点数相等的两部分。(这条线不能通过平面内任何一点)
sample input:
1
4
0 1
-1 0
1 0
0 -1
sample output:(special judge)
-1 999000000 1 -999000001
题解:
将这n个点以x为第一关键字y为第二关键字从小到大排序,找到中间两个点a和b,以这两个点为分界,可发现始终有一条通过a和b中点的很陡的直线可以将平面内的点分成点数相等的两部分。
若排序后中间a、b两点的x坐标不一样,则随便一条划在a、b两点之间的直线都可以;若排序后中间a、b两点的x坐标一样,则一定要过a、b中点的直线才行。
Code:
#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);
using namespace std;
const int m=;
struct point
{
int x,y;
}p[];
bool cmp(point s1,point s2)
{
if(s1.x==s2.x)return s1.y<s2.y;
else return s1.x<s2.x;
}
int main()
{
IO;int T,n;
cin>>T;
while(T--)
{
int x1,y1,x2,y2;
cin>>n;
for(int i=;i<n;i++)
cin>>p[i].x>>p[i].y;
sort(p,p+n,cmp);
if(p[n/].x!=p[n/-].x)
x1=p[n/-].x,y1=m,x2=p[n/].x,y2=-m;
else
x1=p[n/].x-,y1=p[n/].y+m,x2=p[n/].x+,y2=p[n/-].y-m;
cout<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<endl;
}
return ;
}