题解 P7918 【 [Kubic] Lines】

· · 题解

更新于 2021 年 11 月 14 日：增加了正确的代码。

对于 Subtask 3，观察发现只要输出水平直线和竖直直线中较少的那一组即可。这启示我们从平行线的角度分析问题：

我们把倾斜角相同的直线都归为一组，也就是说每一组里所有的直线互相平行。（如果某一条直线没有与之倾斜角相同的直线则单独记为一组）

考虑如果要取到所有交点，可以对于某一组平行线，选出这组线以外的直线。因为平行线间没有交点，所以这种选法已经覆盖了所有的交点，不需要在这一组平行线内选。

因此分组，记录平行线数量最大的那一组，选剩下的即可。

但是有两种比较特殊的情况：

1.\gcd(a,b)\neq1 2.b=0

对于情况一可以约分，也可以像我这样屑一个 double 关键字的 map：

map<double,int> m;
m[(double)a[i]/b[i]]++;

由于原数据太水。double 做法没有被卡精度。

对于情况二特别记录即可。

这是现场的 错误的 屑代码，它非常的屑，很容易看出问题：

#include<cstdio>
#include<map> 
using namespace std;
int read()
{
    int s=0,b=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') b=-1; c=getchar();}
    while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
    return s*b;
}
map<double,int> m;
int n,maxx,s,t,a[100010],b[100010],c[100010];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),b[i]=read(),c[i]=read(),a[i]&&b[i]?m[(double)a[i]/b[i]]++:(!a[i]?s++:t++);//a,b都不为0，则记录水平或竖直
    for(int i=1;i<=n;i++) if(a[i]&&b[i]) maxx=max(maxx,m[(double)a[i]/b[i]]);//找最大的平行线组
    printf("%d\n",s+t==n?min(s,t):n-maxx);//判断输出
    return 0;
 }

是的，它记录了 b=0 的直线数，但没有单独拿出来判断，这是我拿了 90 分后看到了 Subtask 3 写的特判。说明一下这道题的数据很水 qaq

附一组简单的 hack

4
1 0 1
1 0 2
1 0 3
1 1 1

应输出：1

正确的代码应使用约分的方法，如下：

#include<cstdio>
#include<algorithm>
#include<map> 
using namespace std;
int read()
{
    int s=0,b=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') b=-1; c=getchar();}
    while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
    return s*b;
}
map<pair<int,int>,int> m;//索引改为分子和分母！
pair<int,int> f(int x,int y) {return make_pair(x/__gcd(x,y),y/(__gcd(x,y)));} //约分
int n,maxx,s,t,a[100010],b[100010],c[100010];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)//以下操作相同。
        a[i]=read(),b[i]=read(),c[i]=read(),a[i]&&b[i]?m[f(a[i],b[i])]++:(!a[i]?s++:t++);
    for(int i=1;i<=n;i++) if(a[i]&&b[i]) maxx=max(maxx,m[f(a[i],b[i])]);
    printf("%d\n",s+t==n?min(s,t):n-maxx);
    return 0;
 }