L3-012 水果忍者 (30 分)

2010年风靡全球的“水果忍者”游戏，想必大家肯定都玩过吧？（没玩过也没关系啦~）在游戏当中，画面里会随机地弹射出一系列的水果与炸弹，玩家尽可能砍掉所有的水果而避免砍中炸弹，就可以完成游戏规定的任务。如果玩家可以一刀砍下画面当中一连串的水果，则会有额外的奖励，如图1所示。

图 1

现在假如你是“水果忍者”游戏的玩家，你要做的一件事情就是，将画面当中的水果一刀砍下。这个问题看上去有些复杂，让我们把问题简化一些。我们将游戏世界想象成一个二维的平面。游戏当中的每个水果被简化成一条一条的垂直于水平线的竖直线段。而一刀砍下我们也仅考虑成能否找到一条直线，使之可以穿过所有代表水果的线段。

图 2

如图2所示，其中绿色的垂直线段表示的就是一个一个的水果；灰色的虚线即表示穿过所有线段的某一条直线。可以从上图当中看出，对于这样一组线段的排列，我们是可以找到一刀切开所有水果的方案的。

另外，我们约定，如果某条直线恰好穿过了线段的端点也表示它砍中了这个线段所表示的水果。假如你是这样一个功能的开发者，你要如何来找到一条穿过它们的直线呢？

输入格式：

输入在第一行给出一个正整数N（≤10​4​​），表示水果的个数。随后N行，每行给出三个整数x、y​1​​、y​2​​，其间以空格分隔，表示一条端点为(x,y​1​​)和(x,y​2​​)的水果，其中y​1​​>y​2​​。注意：给出的水果输入集合一定存在一条可以将其全部穿过的直线，不需考虑不存在的情况。坐标为区间 [−10​6​​,10​6​​) 内的整数。

输出格式：

在一行中输出穿过所有线段的直线上具有整数坐标的任意两点p​1​​(x​1​​,y​1​​)和p​2​​(x​2​​,y​2​​)，格式为 x​1​​y​1​​x​2​​y​2​​。注意：本题答案不唯一，由特殊裁判程序判定，但一定存在四个坐标全是整数的解。

输入样例：

5
-30 -52 -84
38 22 -49
-99 -22 -99
48 59 -18
-36 -50 -72

输出样例：

-99 -99 -30 -52

解法：总体思想就是先在给出的某一条线段上固定一个端点，以该端点来遍历其他所有线段，通过该端点与其它线段的两个端点相连来确定斜率范围，看是否存在一个斜率范围可以同时穿过所有线段(也就是这个斜率范围，是在该端点与其他任意线段的两个端点连线的斜率范围内的)。 

代码：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n;
double maxk, mink, ansmaxk, ansmink, ansx, ansy;
struct line {double x, maxy, miny;
}l[10010];
int cmp(line a, line b) {if(a.x < b.x) return 1;return 0;
}
int main() {scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%lf%lf%lf", &l[i].x, &l[i].maxy, &l[i].miny);sort(l, l+n, cmp);//排一下序，使所有线段按x坐标从小到大排好 for(int i = 0; i < n; i++) {//把该线段上的点作为答案直线上的一个点 ansmaxk = inf;//初始化经过该线段上点的答案斜率范围 ansmink = -inf;int j;for(j = 0; j < n; j++) {if(i != j) {if(i < j) {//得到可以同时穿过线段i和j的答案直线的斜率范围 maxk = (l[i].miny - l[j].maxy) / (l[i].x - l[j].x);mink = (l[i].miny - l[j].miny) / (l[i].x - l[j].x);} else {maxk = (l[j].miny - l[i].miny) / (l[j].x - l[i].x);mink = (l[j].maxy - l[i].miny) / (l[j].x - l[i].x);}if(ansmaxk < mink || ansmink > maxk) break;//以i线段为基础的答案斜率不满足当前同时穿过两线段的斜率范围，说明不能穿过所有线段，直接breakif(maxk < ansmaxk) {ansmaxk = maxk;ansx = l[j].x;ansy = l[j].maxy;} ansmink = max(mink, ansmink);}} if(j == n) {//存在经过i线段上点的一个斜率范围所得到的答案直线可以同时穿过所有线段 printf("%.0lf %.0lf %.0lf %.0lf\n", l[i].x, l[i].miny, ansx, ansy); //线段i上取了最低点，则另一条线段要取最高点 return 0;}}
}