CodeForces - 593B Anton and Lines (數學方程&技巧) 判斷直線是否相交

CodeForces - 593B Anton and Lines Time Limit: 1000MS Memory Limit: 262144KB 64bit IO Format: %I64d & %I64u Submit Status Description The teacher gave Anton a large geometry homework, but he didn't do it (as usual) as he participated in a regular round on Codeforces. In the task he was given a set of n lines defined by the equations y = ki·x + bi. It was necessary to determine whether there is at least one point of intersection of two of these lines, that lays strictly inside the strip between x1 < x2. In other words, is it true that there are 1 ≤ i < j ≤ n and x', y', such that: y' = ki * x' + bi, that is, point (x', y') belongs to the line number i; y' = kj * x' + bj, that is, point (x', y') belongs to the line number j; x1 < x' < x2, that is, point (x', y') lies inside the strip bounded by x1 < x2. You can't leave Anton in trouble, can you? Write a program that solves the given task. Input The first line of the input contains an integer n (2 ≤ n ≤ 100 000) — the number of lines in the task given to Anton. The second line contains integers x1 and x2 ( - 1 000 000 ≤ x1 < x2 ≤ 1 000 000) defining the strip inside which you need to find a point of intersection of at least two lines. The following n lines contain integers ki, bi ( - 1 000 000 ≤ ki, bi ≤ 1 000 000) — the descriptions of the lines. It is guaranteed that all lines are pairwise distinct, that is, for any two i ≠ j it is true that either ki ≠ kj, orbi ≠ bj. Output Print "Yes" (without quotes), if there is at least one intersection of two distinct lines, located strictly inside the strip. Otherwise print "No" (without quotes). Sample Input Input 4 1 2 1 2 1 0 0 1 0 2 Output NO Input 2 1 3 1 0 -1 3 Output YES Input 2 1 3 1 0 0 2 Output YES Input 2 1 3 1 0 0 3 Output NO Hint In the first sample there are intersections located on the border of the strip, but there are no intersections located strictly inside it. Source Codeforces Round #329 (Div. 2) //題意：直線方程為y=k*x+b. 先輸入n，再輸入x1,x2（左端點、右端點的橫坐标，y1,y2可以根據下面給的k,b求出）,然後輸入n組數，每組數都是k  b。問組成的這n條直線是否會相交。 //思路： 首先根據方程和給出的k  b求出y1,y2，将其存入結構體中，将其排序，在周遊這n條直線，如果不平行，就證明相交了。 #include<stdio.h> #include<math.h> #include<string.h> #include<algorithm> #define INF 0x3f3f3f3f #define ll long long #define N 100010 #define M 1000000007 using namespace std; struct zz { ll l; ll r; }p[N]; int cmp(zz a,zz b) { if(a.l==b.l) return a.r<b.r; return a.l<b.l; } int main() { int n; while(scanf("%d",&n)!=EOF) { ll l,r,k,b; scanf("%lld%lld",&l,&r); for(int i=0;i<n;i++) { scanf("%lld%lld",&k,&b); ll y1=l*k+b; ll y2=r*k+b; p[i].l=y1;p[i].r=y2; } int flag=0; sort(p,p+n,cmp); for(int i=1;i<n;i++) { if(p[i].r<p[i-1].r)//因為左端點在排序後已經嚴格按照從小到大的順序排好序了，隻用判斷右端點就行了。 { flag=1; break; } } printf(flag?"YES\n":"NO\n"); } return 0; }