Bzoj 1610(计算几何+排序去重)

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$为最小误差值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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;
}

------ 本文结束 ------