Magic Line
题目链接（传送门） 来源：牛客网
题目描述
There are always some problems that seem simple but is difficult to solve.
ZYB got N\ N N distinct points on a two-dimensional plane. He wants to draw a magic line so that the points will be divided into two parts, and the number of points in each part is the same. There is also a restriction: this line can not pass through any of the points.
Help him draw this magic line.
输入描述:
There are multiple cases. The first line of the input contains a single integer T (1≤T≤10000)T \ (1 \leq T \leq 10000)T (1≤T≤10000), indicating the number of cases. For each case, the first line of the input contains a single even integer N (2≤N≤1000)N \ (2 \leq N \leq 1000)N (2≤N≤1000), the number of points. The following $N$ lines each contains two integers xi,yi (∣xi,yi∣≤1000)x_i, y_i \ (|x_i, y_i| \leq 1000)xi,yi (∣xi,yi∣≤1000), denoting the x-coordinate and the y-coordinate of the i\ i i-th point.It is guaranteed that the sum of N\ N N over all cases does not exceed 2×1052 \times 10^52×105.
输出描述:
For each case, print four integers x1,y1,x2,y2x_1, y_1, x_2, y_2x1,y1,x2,y2 in a line, representing a line passing through (x1,y1)(x_1, y_1)(x1,y1) and (x2,y2)(x_2, y_2)(x2,y2). Obviously the output must satisfy (x1,y1)≠(x2,y2)(x_1,y_1) \ne (x_2,y_2)(x1,y1)=(x2,y2).The absolute value of each coordinate must not exceed 10910^9109. It is guaranteed that at least one solution exists. If there are multiple solutions, print any of them.
输入
1
4
0 1
-1 0
1 0
0 -1输出
-1 999000000 1 -999000001题目描述：
给出很多坐标点，要求找出一条线使其二等分所有点（线上不能有输入的坐标点），输出线上任意两点坐标。
思路：
a.将所有点排序，找到 n/2 的p点的坐标，再按下图操作。
b.当找到p（x，y）后，由于点的坐标范围是[-1000~1000]，所以先找到点A（x+1,1e7）和点B（x-1，y1）可以根据斜率求出 点B坐标，这样可以满足p点在线上且线上有且仅有一点p。
c.过点AB的这条线是恰好过p点（所有点的中点），所以B的纵坐标-1则恰好不过这个点，也就满足了线上没有点的要求。
思路很简单，但点排序的时候遇到问题：
1、如果按照蓝线方向排序：
bool cmp(node a,node b)
{
if(a.x==b.x){
return a.y>b.y;
}return a.x<b.x;
}2、按照与蓝线垂直方向排序：
bool cmp(node a,node b)
{
if(a.x==b.x){
return a.y<b.y;
}return a.x<b.x;
}AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAX=2e5;
struct node{
LL x;
LL y;
}point[MAX+5];
bool cmp(node a,node b)
{
if(a.x==b.x){
return a.y>b.y;
}return a.x<b.x;
}
int main()
{
LL t,n;
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
for(LL i=0;i<n;i++){
scanf("%lld%lld",&point[i].x,&point[i].y);
}
sort(point,point+n,cmp);
LL ans=n/2-1;
printf("%lld 10000000 %lld %lld\n",point[ans].x+1,point[ans].x-1,2*point[ans].y-10000000-1);
}
return 0;
}
