程序设计天梯赛L3-12 (思维+枚举)

题目 题意: 给定n个线段，找到一条直线，可以一刀斩所有线段。(经过每个线段内一点，端点也可以) 思路: 计算几何一如既往的不会，直接n^3暴力骗分，骗了25分，老骗子了。考虑一下正解。 尽可能地输出整数坐标，可以输出线段对应的端点。   ①固定某个线段的下端点，以他为起点向其他n-1条线段的上下端点连线，计算斜率k1、k2。将k1、k2对应的斜率区间不停的缩小(其实是在取交集。)

  ②如果出现了k1、k2不在维护的斜率区间[min,max]内，说明为了能切到这条线段，前边维护的那些线段都无法切到，说明不符合题意。

时间复杂度: O(n*n) 代码:

#include
using namespace std;
typedef long long ll;
typedef pair PII;
const int N = 1e4+10;
int n,m,k,T;
struct node{
	int x,y1,y2;
	bool operatorn;
	for(int i=0;i>a[i].x>>a[i].y1>>a[i].y2;
		if(a[i].y1 > a[i].y2) swap(a[i].y1,a[i].y2);
	}
	sort(a,a+n);
	for(int i=0;i