专做排版网站/电商网址

http://codeforces.com/contest/593

 题意：n,x1,x2给出，后面是n条定义为形如k*x+b的线，问在x1,x2之间这些线有没有交叉点；

按照纯暴力方法会超时的，所以就要用到一些小技巧：把所有的线在x1,x2之间的区域求出来并按照起点从小到大排序，如果起点大的那条线终点小于起点小的，意味着他们有交叉点；

有一点是刚开始的时候没想明白，就是为什么两两相比就可以，后来想明白了，如果一条在上面的边和下面的边交叉首先就要交叉和他离得最近的那条边，如果交叉不到，只能说明，离他最近的那条边已经和下面的边有过交叉了。

说的太搓了。。（哭惹

AC代码：

#include <stdio.h>
#include <algorithm>
using namespace std;
pair<long long,long long >s[101101];//类似于结构体
int main()
{int n,x1,x2;long long a,b;while(~scanf("%d",&n))//感觉自己好笨，不会再爱了；
    {scanf("%d%d",&x1,&x2);for(int i=0; i<n; i++){scanf("%lld%lld",&a,&b);s[i]=make_pair(a*x1+b,a*x2+b);//用起来超级方便
        }sort(s,s+n);int f=0;for(int i=1; i<n; i++)//根据左边的点从小到大排序，如果一条边左边的点在他上面，右边的点在他下面，那么就认为他们是在x1,x2有交叉点；
        {if(s[i].second<s[i-1].second){f=1;break;}}if(f==1){printf("YES\n");}else{printf("NO\n");}}return 0;
}