站长百科 【BZOJ】1610: [Usaco2008 Feb]Line连线游戏 正文

【BZOJ】1610: [Usaco2008 Feb]Line连线游戏

2022-12-24,,,,

【算法】计算几何

【题解】计算所有斜率排序去重。

实数判断相等用fabs(...)≤eps。

★斜率题一定要注意斜率不存在的情况！！！

其实我觉得这份代码可以hack的……

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const double eps=1e-,inf=1e20;

const int maxn=;

int n,x[maxn],y[maxn],im=,m=;

double a[maxn];

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d%d",&x[i],&y[i]);

    for(int i=;i<=n;i++)

        for(int j=i+;j<=n;j++)

            if(x[i]==x[j])a[++m]=inf;else a[++m]=1.0*(y[i]-y[j])/(x[i]-x[j]);

    sort(a+,a+m+);

    int ans=;

    for(int i=;i<=m;i++)if(fabs(a[i]-a[i-])>eps)ans++;

    printf("%d",ans);

    return ;

}

【BZOJ】1610: [Usaco2008 Feb]Line连线游戏的相关教程结束。

《【BZOJ】1610: [Usaco2008 Feb]Line连线游戏.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!