题目链接：PTA | 程序设计类实验辅助教学平台
f
分析：这道题目我们先来看一下满足题意的直线具有什么样的特殊性质，假如直线l可以过这n条线段，假设l不经过任意一条线段的下端点，那么我们就可以将其向下平移直至经过一条线段的下端点，这个时候不能继续向下平移，但是我们可以绕着所经过的那个下端点进行旋转直至经过另一条线段的端点，也就是说如果存在解，我们就能构造出另一种解使其经过两条线段的端点（上下端点无所谓），这样就解决了答案要求的四个坐标全是整数解的情况。
具体是什么意思呢？就是说我们任意选择一条线段，假设存在一条直线经过其下端点且满足题意，然后与其他线段的端点进行连线求取目标直线斜率范围，由于我们已经知道了目标直线经过的一个点，然后将这个点与一条线段的两个端点连线形成两条直线，这两条直线分别对应着一个斜率，只要最后直线的斜率位于两条直线斜率之间即可经过该线段，这样我们就能一直缩小目标直线的斜率范围，如果最后斜率可取的最大值大于斜率可取的最小值那就说明存在满足题意的直线使其经过我们一开始所假设的线段的下端点。由于我们是在过程中对目标直线的斜率范围进行缩小的，所以当我们当前遍历的线段对目标直线的斜率范围进行缩小时，说明当前线段的端点可以作为目标直线所经过的一个点，如果当前遍历点与当前遍历线段所形成的两条直线的斜率范围包含目标直线的斜率范围，则不会对目标直线的斜率范围造成任何影响，我们只需要在过程中对更新目标区间的端点进行记录即可，再最后如果目标直线的区间长度是正的就输出，否则就继续遍历下一条线段的下断点直至找到满足题意的直线。
下面是代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1e4+10;
struct node{
int x,y1,y2;
}p[N];
bool cmp(node a,node b)
{
return a.x<b.x;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d%d%d",&p[i].x,&p[i].y1,&p[i].y2);
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;i++)
{
double kmin=-0x3f3f3f3f,kmax=0x3f3f3f3f;
double tmin,tmax;
int tx,ty;
bool flag=true;
for(int j=1;j<=n;j++)
{
if(p[i].x==p[j].x) continue;
if(i>j)
{
tmax=(double)(p[i].y2-p[j].y2)/(p[i].x-p[j].x);
tmin=(double)(p[i].y2-p[j].y1)/(p[i].x-p[j].x);
if(tmax<kmax)//斜率最大值被更新，记录更新斜率最大值的端点
{
kmax=tmax;//斜率最小值被更新，记录更新斜率最小值的端点
tx=p[j].x;ty=p[j].y2;//记录临界点坐标
}
if(tmin>kmin)
{
kmin=tmin;
tx=p[j].x;ty=p[j].y1;//记录临界点坐标
}
}
else
{
tmax=(double)(p[j].y1-p[i].y2)/(p[j].x-p[i].x);
tmin=(double)(p[j].y2-p[i].y2)/(p[j].x-p[i].x);
if(tmax<kmax)//斜率最大值被更新，记录更新斜率最大值的端点
{
kmax=tmax;
tx=p[j].x;ty=p[j].y1;//记录临界点坐标
}
if(tmin>kmin)//斜率最小值被更新，记录更新斜率最小值的端点
{
kmin=tmin;
tx=p[j].x;ty=p[j].y2;//记录临界点坐标
}
}
if(tmin>kmax||tmax<kmin||kmax<kmin)//出现无解，也就是说不存在过第i条直线的下端点的直线满足题意
{
flag=false;
break;
}
}
if(flag)
{
printf("%d %d %d %d",p[i].x,p[i].y2,tx,ty);
break;
}
}
return 0;
}