Magic Line【坐标点排序方法】

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 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;

}

巴特西

Magic Line【坐标点排序方法】

Magic Line

最新文章

热门文章