ACM训练——Colorful Rainbows

题目链接：https://vjudge.net/problem/ZOJ-2967

 Evelyn likes drawing very much. Today, she draws lots of rainbows on white paper of infinite size, each using a different color. Since there're too many rainbows now, she wonders, how many of them can be seen?

For simplicity, each rainbow Li is represented as a non-vertical line specified by the equation: y=aix+bi. A rainbow Li can be seen if there exists some x-coordinate x0 at which, its y-coordinate is strictly greater than y-coordinates of any other rainbows: aix0+bi > ajx0+bj for all j != i.

Now, your task is, given the set of rainbows drawn, figure out the number of rainbows that can be seen.

Input

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 60) which is the number of test cases. And it will be followed by T consecutive test cases.

There's a blank line before every case. In each test case, there will first be an integer n (1 <= n <= 5000), which is the number of rainbows. Then n consecutive real number pairs follow. Each pair contains two real numbers, ai and bi, representing rainbow Li: y=aix+bi. No two rainbows will be the same, that is to say, have the same a and b.

Output

Results should be directed to standard output. The output of each test case should be a single integer, which is the number of rainbows that can be seen.

Sample Input

2

1
1 1

3
1 0
2 0
3 0

Sample Output

1
2

 暴力解法：依次判断每条直线是否可以在某一个区间(l,r)内作为所有直线中的最高点，那么主要的任务就是求(l,r)

                  （1）如果L1的的斜率等于L2的斜率，这羊样直接看截距，和(l,r)没关系

                  （2）如果L1的斜率大于L2的斜率，假设交点为x0,那么区间(x0,+INF)内y1>y2(函数值)，那么相对于L1来说，                                 l=max(l,x0).更新l。

                  （3）如果L1的斜率小于L2的斜率，假设交点为x0,那么区间(-INF,x0)内y1>y2(函数值)，那么相对于L1来说，                                 r=min(r,x0).更新r。

最后判断一条直线可不可以存在合理的(l,r)就可以看出该直线是否是答案中的一员

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const double INF=-10000000000000000;
double a[5010],b[5010];
bool vis[5010];//vis[j]=true表示直线j已经不可能作为最大值
int main()
{
    IOS;
    ll t;
    ll n;
    double temp,l,r;
    cin>>t;
    while(t--){
        memset(vis,false,sizeof(vis));
        cin>>n;
        ll ans=0;
        for(int i=0;i<n;i++){
            cin>>a[i]>>b[i];
        }
        //我们把每条直线作为最高值出现所在的x值称为xi。
        for(int i=0;i<n;i++){//遍历每条直线
            if(vis[i])continue;//如果不可能在某个点作为最高点直接遍历下一条
            l=INF;//初始化xi的范围(负无穷,正无穷)
            r=-INF;
            int j;
            //和其他直线比较，更新l,r
            for(j=0;j<n;j++){
                if(i==j)continue;
                if(a[i]==a[j]){//斜率相等看截距
                    if(b[i]<=b[j])break;
                    else vis[j]=true;//直线j不可能在某处作为最高值
                }
                else {
                    //求出交点
                    temp=(b[j]-b[i])/(a[i]-a[j]);
                    if(a[i]>a[j]){//更新xi的左界
                        l=max(l,temp);
                        if(l>=r)break;//l必须小于r才有可能
                    }
                    else {//更新xi的右界
                        r=min(r,temp);
                        if(l>=r)break;
                    }
                }
            }
            if(j==n)ans++;//没有提前退出，说明该直线在(l,r)内值最大
        }
        cout<<ans<<endl;
    }
    getchar();
    getchar();
    return 0;
}