PAT 1. 枚举斜率
原题链接
简单
作者:
流动的音符
,
2024-04-18 21:07:39
,
所有人可见
,
阅读 2
题解
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
struct seg{ double x, y1, y2; }s[maxn];
bool cmp(seg a, seg b){
return a.x<b.x;}
double maxk,mink,ansmaxk,ansmink,ansx,ansy;
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++)
cin>>s[i].x>>s[i].y1>>s[i].y2;//y1在上,y2在下
//按照x下标排序
sort(s+1,s+n+1,cmp);
for(int i = 1; i <= n; i++){
//枚举每个水果,最低点,与其他边连线的斜率最小值,最大值
ansmaxk = 1e9;
ansmink = -1e9;
int j;
for(j = 1; j <= n; j++){
if(j==i)continue;
if(i<j){// j在i右侧
maxk = (s[i].y2-s[j].y1)/(s[i].x-s[j].x);//
mink = (s[i].y2-s[j].y2)/(s[i].x-s[j].x);
}else{ //j在i左侧
maxk = (s[i].y2-s[j].y2)/(s[i].x-s[j].x);
mink = (s[i].y2-s[j].y1)/(s[i].x-s[j].x);
}
if(ansmaxk<mink || ansmink>maxk)break;
if(maxk<ansmaxk){
//不能满足限制条件的时候更新限制,即把ansk往下调
ansmaxk = maxk;
ansx = s[j].x;
ansy = s[j].y1;
}
ansmink = max(ansmink, mink);
}
if(j==n+1){//存在解
//线段i上取了最低点,则另一条线段要取最高点
printf("%.0lf %.0lf %.0lf %.0lf\n",s[i].x,s[i].y2,ansx,ansy);
return 0;
}
}
return 0;
}