[开发工具]2021杭电多校3

T1004 Game on Plane

题意：给n条直线，每轮一个k，A先选k条，B再画一条，计算B画的这条线与A选的这k条线的交点，A希望这个值尽可能大，B反之。问k从1到n递增时候，这个最小为多少。

idea：
1)HDOJ不要用读入优化 ！！！！
（如图：）

2）cmp别别手欠多打个=

ACcode:

#include <cstdio>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define x first
#define y second
#define PII pair<LL,LL>

using namespace std;
PII u,v,AB;
LL t,num[1001010];

LL gcd(LL a,LL b)
{
	LL c;
    while( b )
    {
    	c = a;
    	a = b;
    	b = c%a;
	}
	return a;
}
LL n,m;
PII jian( PII a,PII b )
{
    PII ans,temp;
    ans.x = b.x-a.x;
    ans.y = b.y-a.y;
    if( ans.x<0 )
    {
        ans.x = -ans.x;
        ans.y = -ans.y;
    }
    temp = ans;
    if( temp.x<0 ) temp.x = -temp.x;
    if( temp.y<0 ) temp.y = -temp.y;
    LL g = gcd( temp.x , temp.y );
    ans.x /= g;
    ans.y /= g;
    return ans;
}
bool cmp(LL x,LL y)
{
    return x>y;
}
LL tot = 0;
map<PII,LL> ma1;
int bucket[100010];
void solve()
{
    tot = 0;
    ma1.clear();
    scanf("%lld",&n);
    for(LL i=1;i<=n;i++)
    {
        scanf("%lld %lld %lld %lld",&u.x,&u.y,&v.x,&v.y);

        if( u.x==v.x )
        {
            AB.x = 0;
            AB.y = 1;
        }
        else if( u.y==v.y )
        {
            AB.x = 1;
            AB.y = 0;
        }
        else AB = jian( u,v );

        if( ma1[AB]==0 )
        {
            tot++;
            num[tot] = 0;
            ma1[AB] = tot;
            num[tot]++;
        }
        else
        {
            LL tag = ma1[AB];
            num[tag]++;
        }
    }

    sort(num+1,num+tot+1,cmp);

    LL j = 1,maxx=0,h = 1;
    for(;j<=tot;j++)
    {
        h++;
        num[j]--;
        printf("%lld\n",j-1);
    }
    
    maxx = j-2;
    for(;h<=n;j++)
    {
        h++;
        if( j>tot||num[j]==0 )
        {
            j = 1;
        }
        num[j]--;
        if( j==1 )
        {
            printf("%lld\n",maxx);
        }
        else
        {
            maxx++;
            printf("%lld\n",maxx);
        }
    }

}
int main()
{
    scanf("%lld",&t);
    while( t-- )
        solve();
    return 0;
}

（后面补T1010… ）