看着别人的题解又学习了一遍…原文题解
感觉我再多说废话反而更难理解…

算法

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e4+10;

struct Node{
    double x,y1,y2;
}p[N];

int n;

bool cmp(struct Node a,struct Node b)
{
    return a.x<b.x;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>p[i].x>>p[i].y1>>p[i].y2;
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        double k1 = 0,k2 = 0;
        double k_max = 0x3f3f3f3f,k_min = -0x3f3f3f3f;
        double x = 0,y = 0;
        int j = 1;
        for(j=1;j<=n;j++)
        {
            if(i==j)    continue;
            if(j>i)
            {
                k1 = (p[j].y1-p[i].y2)/(p[j].x-p[i].x);
                k2 = (p[j].y2-p[i].y2)/(p[j].x-p[i].x);
            }
            else
            {
                k1 = (p[j].y2-p[i].y2)/(p[j].x-p[i].x);
                k2 = (p[j].y1-p[i].y2)/(p[j].x-p[i].x);
            } 
            if(k1<k_min||k2>k_max)  break;
            if(k1<k_max)    
            {
                k_max = k1;
                x = p[j].x;
                if(j>i) y = p[j].y1;
                else y = p[j].y2;
            }
            if(k2>k_min)
            {
                k_min = k2;
                x = p[j].x;
                if(j>i) y = p[j].y2;
                else y = p[j].y1;
            }
        }
        if(j==n+1)//一定要格式化输出，不然有一个点过不去
        {
            printf("%.0lf %.0lf %.0lf %.0lf",p[i].x,p[i].y2,x,y);
            break;
        }
    }
    return 0;
}