「Bzoj 1610」「Usaco2008 Feb」Line连线游戏 (计算几何+排序去重)

BZOJ 1610
Luogu 2665
from: USACO 2008 Feb Sliver(USACO刷题第17题)

刚开始想到搜索每个点然后求斜率…然后并不行
看题解以后直接全部求出来排序去重就可以了…

求斜率公式：$$k = \frac{y_1-y_2}{x_1-x_2}$$
推导过程：设两个点为$(x_1, y_1),(x_2, y_2)$，它们之间连线的解析式为$y=kx+b$
将两点坐标带入解析式，得$y_1=kx_1+b, y_2=kx_2+b$
$y_1- y_2$，得$ y_1-y_2=kx_1-kx_2$
$k(x_1-x_2) = y_1-y_2$
即$k = \frac{y_1-y_2}{x_1-x_2}$

注意，比较两个浮点数的大小为$fabs(a-b)<eps$即相等, $eps$为最小误差值

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;

const int MAXN = 200 + 5;
const double INF = 1000000000.0, eps = 1e-8;

int n, px[MAXN], py[MAXN], tot; 
double xl[MAXN*MAXN];

void clean() {
    tot = 0;
    xl[0] = INF;
}
void init() {
    clean();
    for (int i=1;i<=n;i++) scanf("%d%d", &px[i], &py[i]);
}
void solve() {
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++) 
    if (i!=j) {
        if (px[i]==px[j]) xl[++tot] = INF; 
            else xl[++tot] = (double)(py[i]-py[j])/(double)(px[i]-px[j]);
    }
    sort(xl+1, xl+1+tot);
    int ans = 0;
    for (int i=1;i<=tot;i++) if (fabs(xl[i]-xl[i-1])>eps) ans++;
    printf("%d\n", ans);
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d", &n)==1) init(), solve();
    return 0;
}