菜鸟题解 HDU-6882 Divide and Conquer

原题直达

https://vjudge.net/contest/582185#problem/J

题干

原题面
参考翻译

Given n points in plane, where , 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 given points. If multiple solutions exist, print any one of them. If no solution, print "-1" in one line.

Input

The first line contains one positive integer , denoting the number of test cases. For each test case:

The first line contains one integer , denoting the number of given points.

Following n lines each contains two integers , denoting one given point .

It is guaranteed that , that no two points coincide and that no three points are collinear.

Output

For each test case:

If no solution, print "-1" in one line. Else print two lines each containing four integers with absolute value not exceeding , denoting one line passing simultaneously.

给定平面上的个点，其中，没有两个点重合，没有三个点共线。找出两条相交的直线，满足两条直线上没有给定的点，并且对于四个划分的区域中的每一个，都有给定的点。如果存在多个解决方案，则打印其中任何一个。如果没有解决方案，在一行中打印“-1”。

Input

第一行包含一个正整数，表示测试用例的数量。对于每个测试用例:

第一行包含一个整数，表示给定点的数量。

下面的n行每行包含两个整数，表示一个给定的点。

可以保证，没有两个点重合，没有三个点共线。

Output

对于每个测试用例:

如果没有解决方案，在一行中打印“-1”。否则打印两行，每行包含四个整数 $，$ ，绝对值不超过，表示一行同时传递 $，$ 。

测试案例

Input

Output

题意与思路

给定个点，其中是的倍数，任意两点不重合、任意三点不共线，要求在平面上找到两条相交的直线，这两条直线将平面划分为4个区域，每个区域恰好都有个点。

对于某一条直线，通过 两点确定一条直线 的原则来定义，即给出两个点的坐标，来表征这一条直线。

我们考虑 先找一条直线将所有点平均分为两部分，再找第二条条直线将这两部分各自平分为两部分。

先找第一条直线

两条直线不好找，一条直线就没那么难了：

当位于中间的两个点 纵坐标不同 时，将它们的 纵坐标分别增加和减少一个足够大的值 ，得到第一条平分线
当位于中间的两个点 纵坐标相同 时，将它们的 横坐标分别增加和减少一个偏移量 ，再执行上一条选项，得到第一条平分线

两种构造方式

按照这样办法找到的直线位于中间的两点之间，只要足够大，这条直线将会无限接近于 垂直 x 轴，因此它 不会经过其他点。

至此，我们找到了第一条平分线。

ps. 有关的取值，我采用了常量定义的形式尝试，因为本题要求的输出范围为，因此从开始尝试，这一取值对本题的评测案例来说满足题意。

再找第二条直线

找到一条直线后，还需要找到一条与它相交的直线，我们采用下面的思路来二分地查找：

二分查找第二条直线

如上图所示，我们 二分查找第二条直线的斜率，对于任意一个确定的斜率（如下图粗虚线所示），我们将个点按照这一斜率投影到直线上：

将所有点按特定斜率投影到第一条直线上

我们将投影点 按纵坐标从小到大排序，得到新坐标的索引，如上图中：

原坐标索引为的点，新坐标索引为；
原坐标索引为的点，新坐标索引为；

为了更直观地展示，将 来自左半部分的映射索引标记在直线左侧，将 来自右半部分的映射索引标记在直线右侧：

原索引与新索引

因为直线已经将平面上的点平均分为左右两部分，因此左侧和右侧肯定各有个标记，想要找到，须有直线的 左下、右下、左上、右上 各有个标记：

左下、右下、左上、右上各有2个点

观察它们的原索引和新索引，我们可以发现：

在直线左侧 = 原索引不超过
在直线下方 = 新索引不超过

表现为代码，我们只需要按照 新坐标从小到大遍历，记录上述两种点位于左侧还是右侧，当位于左右两侧的点的个数同时达到时，可以认为存在。

如下图所示，当右侧的点率先超过而左侧尚未达到时，说明当前斜率下 左侧下方缺点，因此我们考虑 左侧抬升以使得左下方容纳更多的点：

二分的调整策略

如何使用代码表达

原理讲清楚了，接下来就面临着 如何从数学上懂了转变为代码上懂了。

点的表达

我们采用结构体来表示点：

struct Point{
    double x, y;  // 横, 纵坐标

    Point(){  // 构造函数
        x = 0;
        y = 0;
    }
    Point(double _x, double _y){  // 构造函数
        x = _x;
        y = _y;
    }
    
    // 重定义一些符号, 便于后续的计算和排序
    bool operator <(const Point &b)const{
        return (dcmp(x - b.x) == 0 ? dcmp(y - b.y) < 0 : x < b.x);
    }
    Point operator+(const Point &b)const{
        return Point(x + b.x, y + b.y);
    }
    Point operator-(const Point &b)const{
        return Point(x - b.x, y - b.y);
    }

};

此外，我们还需要另一种数据结构来同时存储点的新、旧索引：

struct Ponit_with_i{
    Point p;  // 点
    int i;  // 原坐标 新坐标直接使用数组下标表示即可
    Ponit_with_i(){}
    Ponit_with_i(Point _p, int _i){
        p = _p;
        i = _i;
    }
    // 按纵坐标从小到大排序
    bool operator<(const Ponit_with_i &b) const{
        return dcmp(p.y - b.p.y) < 0;
    }
};

直线的表达

我们需要通过 两点确定一条直线 的方法来定义直线：

struct Line{
    Point p1, p2;  // 两点确定一条直线
    Line(){

    }
    Line(Point _p1, Point _p2){
        p1 = _p1;
        p2 = _p2;
    }
    
    // 二分查找倾角
    double theta(){  // 直线与x轴正方向的夹角 取值 -pi ~ pi
        return atan2(p2.y - p1.y, p2.x - p1.x);
    }
    
    // 用于求直线交点
    // Ax + By + C = 0
    double getA(){
        return p1.y - p2.y;
    }
    double getB(){
        return p2.x - p1.x;
    }
    double getC(){
        return p1.x * p2.y - p2.x * p1.y;
    }
};

此外，我们还需要确定 点根据指定斜率在直线上的投影，由于 点和斜率可以确定一条直线，进而将问题转化为 求两条直线的交点：

对于任意两条直线和，通过解方程组使用参数表达，可得：将其定义为一个函数：

Point getCrossPoint(Line l1, Line l2){  // 计算两条直线的交点
    double A1 = l1.getA(), B1 = l1.getB(), C1 = l1.getC();
    double A2 = l2.getA(), B2 = l2.getB(), C2 = l2.getC();
    double x_cross = (B1 * C2 - B2 * C1) / (A1 * B2 - A2 * B1);
    double y_cross = (C1 * A2 - C2 * A1) / (A1 * B2 - A2 * B1);

    return Point(x_cross, y_cross);
}

double的精度控制

此外，由于本题涉及双浮点数的计算，我们习惯性地定义一个精度控制函数，来实现等于关系的比较：

inline int dcmp(double x){
    if(fabs(x)<eps) return 0;
    return (x > 0 ? 1 : -1);
}

题解

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const double pi = acos(-1.0);  // 计算 pi
const double eps = 1e-8;
const int maxn = 50010;
const double max_length = 1e6;  // 点的坐标范围
const double max_enough = 9e8;  // 用于把 l1 拉直
const int max_iterator = 50;    // 最大迭代次数

inline int dcmp(double x){
    if(fabs(x)<eps) return 0;
    return (x > 0 ? 1 : -1);
}

struct Point{

    double x, y;

    Point(){
        x = 0;
        y = 0;
    }
    Point(double _x, double _y){
        x = _x;
        y = _y;
    }

    bool operator <(const Point &b)const{
        return (dcmp(x - b.x) == 0 ? dcmp(y - b.y) < 0 : x < b.x);
    }
    Point operator+(const Point &b)const{
        return Point(x + b.x, y + b.y);
    }
    Point operator-(const Point &b)const{
        return Point(x - b.x, y - b.y);
    }

};

struct Line{
    Point p1, p2;  // 两点确定一条直线
    Line(){

    }
    Line(Point _p1, Point _p2){
        p1 = _p1;
        p2 = _p2;
    }
    double theta(){  // 直线与x轴正方向的夹角 取值 -pi ~ pi
        return atan2(p2.y - p1.y, p2.x - p1.x);
    }
    double getA(){
        return p1.y - p2.y;
    }
    double getB(){
        return p2.x - p1.x;
    }
    double getC(){
        return p1.x * p2.y - p2.x * p1.y;
    }
};

Point getCrossPoint(Line l1, Line l2){  // 计算两条直线的交点
    double A1 = l1.getA(), B1 = l1.getB(), C1 = l1.getC();
    double A2 = l2.getA(), B2 = l2.getB(), C2 = l2.getC();
    double x_cross = (B1 * C2 - B2 * C1) / (A1 * B2 - A2 * B1);
    double y_cross = (C1 * A2 - C2 * A1) / (A1 * B2 - A2 * B1);

    return Point(x_cross, y_cross);
}

struct Ponit_with_i{
    Point p;
    int i;
    Ponit_with_i(){}
    Ponit_with_i(Point _p, int _i){
        p = _p;
        i = _i;
    }
    bool operator<(const Ponit_with_i &b) const{
        return dcmp(p.y - b.p.y) < 0;
    }
};


Line l1, l2;
Point p[maxn];
Ponit_with_i pwi[maxn];

int n, T;

int main(){
    scanf("%d", &T);

    while(T--){
        scanf("%d", &n);

        for(int i = 0;i < n;i++)
            scanf("%lf%lf", &p[i].x, &p[i].y);
        // cout<<"input complete!"<<endl;

        sort(p, p+n);  // 所有点按横坐标排序

        // 找中间的两个点 n/2-1 和 n/2, 找一条近似垂直x轴的线将它们分开
        double delta = 0;

        if(p[n/2-1].x == p[n/2].x)  // 中间的两个点恰好在一条垂直线上
            delta = 1.00;  // 偏移
        
        // 两点确定一条直线
        Point p1_l1(p[n/2-1].x - delta, -max_enough);
        Point p2_l1(p[n/2].x + delta, max_enough);
        l1 = Line(p1_l1, p2_l1);

        // 通过点+斜率的形式确定l2
        int p_l2_index = 0;  // 用于确定 l2 的点在p[]中的位置
        double theta_l2 = 0;  // 用于确定 l2 的倾斜角 

        // 二分查找倾斜角
        double left = l1.theta() - pi;
        double right = l1.theta();
        double mid;
        bool isFind = false;
        int cnt = 1;

        while(cnt <= max_iterator && !isFind){
            cnt ++;
            mid = left + (right - left) / 2.00;
            // mid = (right + left) / 2.00;
            // cout<<"cnt = "<<cnt<<", mid = "<<mid<<endl;
            
            Point base(max_length * cos(mid), max_length * sin(mid));  // 基向量
            for(int i = 0;i < n;i++){
                // Point p_across = getCrossPoint(l1, Line(p[i], p[i] + base) );
                pwi[i] = Ponit_with_i(getCrossPoint(l1, Line(p[i], p[i] + base) ), i);  // 绑定坐标
            }

            sort(pwi, pwi + n);
            int l_num = 0;
            int r_num = 0;
            if(pwi[0].i < n / 2) l_num++;
            else r_num ++;

            for(int i = 1;i < n;i++){
                if(dcmp(pwi[i - 1].p.y - pwi[i].p.y) == 0){
                    if(pwi[i].i < n/2) l_num++;
                    else r_num++;
                }
            
                else{
                    if(l_num == n/4 && r_num == n/4){
                        isFind = true;
                        p_l2_index = pwi[i-1].i;
                        theta_l2 = mid;
                        break;
                    }
                    else if(l_num >= n/4){
                        left = mid; break;
                    }
                    else if(r_num >= n/4){
                       right = mid; break;
                    }
                    if(pwi[i].i < n / 2) l_num ++;
                    else r_num ++;
                }
            }
        }

        delta = 0.9999;  // l2不能直接经过点p_l2_index
        Point p2_l2(max_enough * cos(theta_l2), max_enough * sin(theta_l2));
        p[p_l2_index].y += delta;
        l2 = Line(p[p_l2_index] + p2_l2, p[p_l2_index] - p2_l2);
        
        printf("%d %d %d %d\n", (int)round(l1.p1.x), (int)round(l1.p1.y), (int)round(l1.p2.x), (int)round(l1.p2.y));
        printf("%d %d %d %d\n", (int)round(l2.p1.x), (int)round(l2.p1.y), (int)round(l2.p2.x), (int)round(l2.p2.y));
        
    }

    return 0;
}