[牛客暑期多校第三场][思维]H-Magic Line

发布于 2019-07-29  256 次阅读


https://ac.nowcoder.com/acm/contest/883/H

题意:给定N个点的坐标 N是个偶数 画一条线 要求将这N个点分开 一边一半
要求这条线不能穿过点 给出这条线上的两个左边

思路:按照X排序 取极限 具体看咖啡鸡的代码 再%一次咖啡鸡 太强了
如果两个点在同一条竖直线上 这个代码需要想明白

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
#include<sstream>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 9e8;
typedef pair<int, int> pi;
pi arr[1005];

int main() {
	int n, t;
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> arr[i].first >> arr[i].second;
		}
		sort(arr, arr + n);
		if (arr[n / 2 - 1].first < arr[n / 2].first) {//如果中间的两个点不在同一条y上
			printf("%d %d %d %d\n", arr[n / 2 - 1].first, maxn, arr[n / 2], -maxn);//从左上到右下(几乎还是一条竖直的线)
		}
		else {//在同一条Y上
			printf("%d %d %d %d\n", arr[n / 2].first - 1, arr[n / 2].second + maxn, arr[n / 2].first + 1, arr[n / 2 - 1].second - maxn);
		}
	}
	return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。