【BZOJ1610】[Usaco2008 Feb]Line 连线游戏

2014-05-29
竞赛题解 / 模拟
BZOJUSACO

描述 Description

Farmer John 最近发明了一个游戏，来考验自命不凡的贝茜。游戏开始的时 候，FJ 会给贝茜一块画着 N (2 <= N <= 200) 个不重合的点的木板，其中第 i 个点 的横、纵坐标分别为 X_i 和 Y_i (-1,000 <= X_i <=1,000； -1,000 <= Y_i <= 1,000)。 贝茜可以选两个点画一条过它们的直线，当且仅当平面上不存在与画出直线 平行的直线。游戏结束时贝茜的得分，就是她画出的直线的总条数。为了在游戏 中胜出，贝茜找到了你，希望你帮她计算一下最大可能得分。

描述了点 i 的坐标

输出格式 OutputFormat

第 1 行: 输出 1 个整数，表示贝茜的最大得分，即她能画出的互不平行的直线数

样例输入 SampleInput

8
-1 -2
0 1
-3 -4
5 3
-4 -1
2 5
1 0
3 -5

样例输出 SampleOutput

25

来源 Source

Silver

BZOJ 1610

代码 Code

枚举就行。注意精度。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 0x7fffffff
struct point
{
    int z,y,x;
}a[201];
long double b[50001];
int i,j,n,m,l,r,k;
long double t;
bool slope;
int main()
{
    scanf("%d",&n);
    slope=false;
    m=0;
    for (i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
    for (i=1;i<=n;i++) for (j=i+1;j<=n;j++)
    {
        if (a[i].x==a[j].x)
        {
            if (slope==false)
            {
                slope=true;
                b[++m]=inf;
            }
            continue;
        }
        t=((long double)(a[i].y-a[j].y))/(a[i].x-a[j].x);
        for (k=1;k<=m;k++) if (b[k]==t) break;
        if (k<=m) continue;
        b[++m]=t;
    }
    printf("%d\n",m);
    return 0;
}