杭电3：Game on Plane

题面：平面上有n条直线，Alice会进行n次操作，每次选出k条直线(k=1,2,3,…n),Bob将画一条直线，若与选中的直线有交点则惩罚加一。Alice想让惩罚最大，Bob反之。最后输出每次操作的惩罚值。
解析：画出的直线只能是平行关系才没有公共点。Alice每次会尽量选出斜率不一样的直线，若是斜率相同则尽量使相同的种类多。Bob则每次画一条出现斜率最多的直线。
注意:斜率不好直接储存，因为做了除法，可能会出现精度丢失或这除以0的情况。这里可以用pair储存约分后的最简坐标。
不需要直接存相同斜率直线的个数，用j来表示Alice取出直线的阶段，f[j]表示j阶段有多少斜率不同的直线。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> p;
int t,n;
p a[100005];

int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
int f[100006]; 
int i,j,k;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int ans=0,te=0;
        for( i=1;i<=n;i++)
        {
            int  x1,x2,y1,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            int dx=x1-x2,dy=y1-y2;
            if(dx==0) dy=1;
            else if(dy==0) dx=1;
            else { 
            if(dx<0) dy=-dy,dx=-dx;
            int d=gcd(abs(dx),abs(dy));
            dx/=d;dy/=d;
            }
            //cout<<dx<<" "<<dy<<endl;

        a[i]=p(dx,dy);
        }
        sort(a+1,a+1+n);
    for(i=1;i<=n;i++) f[i]=0;
    for(i=1;i<=n;i=j){
        for(j=i;j<=n&&a[i]==a[j];j++);
        for(k=1;k<=j-i;k++) f[k]++;
    }
    for(i=j=1;i<=n;i++){
        while(f[j]==0) j++;
        f[j]--;
        cout<<i-j<<endl;
    }

    }
}