Magic Line

There are multiple cases. The first line of the input contains a single integer $T \ (1 \leq T \leq 10000)$ , indicating the number of cases.

For each case, the first line of the input contains a single even integer $N \ (2 \leq N \leq 1000)$ , the number of points. The following $N$ lines each contains two integers $x_i, y_i \ (|x_i, y_i| \leq 1000)$ , denoting the x-coordinate and the y-coordinate of the $\ i$ -th point.

It is guaranteed that the sum of $\ N$ over all cases does not exceed $2 \times 10^5$ .

For each case, print four integers $x_1, y_1, x_2, y_2$ in a line, representing a line passing through $(x_1, y_1)$ and $(x_2, y_2)$ . Obviously the output must satisfy $(x_1,y_1) \ne (x_2,y_2)$ .

The absolute value of each coordinate must not exceed $10^9$ . It is guaranteed that at least one solution exists. If there are multiple solutions, print any of them.

C++14(g++5.4) 解法, 执行用时: 48ms, 内存消耗: 2400K, 提交时间: 2020-06-21 16:24:19

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<int,int>p[1005];
int eps=1e8;
main(){
    int n,t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d%d",&p[i].first,&p[i].second);
        sort(p,p+n);
        printf("%d %d %d %d\n",p[n/2-1].first+1,p[n/2-1].second-eps,p[n/2].first-1,p[n/2].second+eps);
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 59ms, 内存消耗: 736K, 提交时间: 2019-07-25 20:00:23

#include<bits/stdc++.h>
using namespace std;
pair<int,int> p[1005];
int EPS=8e8;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d %d",&p[i].first,&p[i].second);
		}
		sort(p+1,p+n+1);
		printf("%d %d %d %d\n",p[n/2].first+1,p[n/2].second-EPS,p[n/2+1].first-1,p[n/2+1].second+EPS);
	}
}

详情