1 条题解

  • 1
    @ 2026-6-12 13:24:11

    太史了

    #include<bits/stdc++.h>
    using namespace std;
    #define N 310
    #define int long long
    #define lint __int128
    #define pii pair<int,int>
    int x[N],y[N];
    map<pair<pii,pii>,bool>v; 
    map<int,bool>v1,v2;
    signed main()
    {
    	ios::sync_with_stdio(0);
    	cin.tie(0);cout.tie(0);
    	int n,k;cin>>n>>k;int ans=0;
    	for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    	if(k==1){cout<<"Infinity";return 0;}
    	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)
    	{
    		if(x[i]==x[j])
    		{
    			if(v1.find(x[i])!=v1.end())continue;
    			v1[x[i]]=1;int cnt=0;
    			for(int t=1;t<=n;t++)if(x[t]==x[i])cnt++;
    			if(cnt>=k)ans++;
    			continue;
    		}
    		if(y[i]==y[j])
    		{
    			if(v2.find(y[i])!=v2.end())continue;
    			v2[y[i]]=1;int cnt=0;
    			for(int t=1;t<=n;t++)if(y[t]==y[i])cnt++;
    			if(cnt>=k)ans++;
    			continue;
    		}
    		int km=y[j]-y[i],kz=x[j]-x[i];
    		int d1=__gcd(km,kz);km/=d1;kz/=d1;
    		int bm=y[i]*kz-x[i]*km,bz=kz;
    		int d2=__gcd(bm,bz);bm/=d2;bz/=d2;
    		if(v.find({{km,kz},{bm,bz}})!=v.end())continue;
    		v[{{km,kz},{bm,bz}}]=1;int cnt=0;
    		int d=__gcd(kz,bz);lint p=kz*bz/d;
    		for(int t=1;t<=n;t++)
    			if(lint(km*p/kz*x[t]+bm*p/bz)==lint(y[t]*p))cnt++;
    		if(cnt>=k)ans++;
    	}
    	cout<<ans;return 0;
    }
    
    • 1

    信息

    ID
    12459
    时间
    2000ms
    内存
    1024MiB
    难度
    10
    标签
    递交数
    181
    已通过
    5
    上传者