P7605 - Divide and Conquer

内存限制：128 MB 时间限制：2 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：0 通过：0

Given

n points in 2D plane, where

n≡0(mod4), no two points coincide and no three points are collinear. Find two intersecting lines satisfying that no given points lie in the two lines and that for each of the four divided areas, there are exactly

n4 given points. If multiple solutions exist, print any one of them. If no solution, print "-1" in one line.

The first line contains one positive integer

T (

1≤T≤20), denoting the number of test cases. For each test case:

The first line contains one integer

n(4≤n≤50000), denoting the number of given points.

Following

n lines each contains two integers

xi,yi(|xi|,|yi|≤106), denoting one given point

(xi,yi).

It is guaranteed that

∑n≤105,n≡0(mod4), that no two points coincide and that no three points are collinear.

For each test case:

If no solution, print "-1" in one line. Else print two lines each containing four integers

x1,y1,x2,y2((x1,y1)≠(x2,y2)) with absolute value not exceeding

109, denoting one line passing

(x1,y1),(x2,y2) simultaneously.

7605: Divide and Conquer

题目描述

输入格式

输出格式

输入样例复制

输出样例复制