简单数学题或者计算几何：Codeforces 659D-Bicycle Race

68 阅读 0 评论 45 点赞

我是靠谱客的博主个性咖啡，最近开发中收集的这篇文章主要介绍简单数学题或者计算几何：Codeforces 659D-Bicycle Race，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Codeforces 659D题目大意如下：

自行车环湖赛，车手围绕湖骑行一周，给出车手骑行的路线的每个转弯处的坐标，同时需要注意的是车手在转弯方向朝向湖的时候有骑进湖里的危险。现在要你根据给出的这些点的坐标，判断车手将会有多少个转弯危险处（每相邻三个点之间的两条路方向都是不同的，而且车手开始的地方是在最西南角）。

给人的第一印象是几何，所以理所当然的想到计算几何，但是之后还有一种非常简单的判断方法，两种现在都写在下面：

1.计算几何法：

从题目的题意可以知道，重点是要分清出湖和陆地，联想到矢量，能够实现这样判断的就是叉乘了。比如对于任意三个相邻的点，我们沿着车手的骑行方向规定为p1, p2, p3，同事也代表了这三个点对应的向量。假设向量A = p2 - p1， B = p3 - p1。那么C = A x B

这里这样理解：如果这个转弯口是对着湖的话，显然会出现C的模小于零的情况；如果这个转弯口是对着陆地的话，就是C的模大于零的情况。

所以可以根据这个对每一个点都计算一次叉乘，统计C的模小于零的数量，代码如下（Accept：15MS / 2200KB）：

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n, x[maxn], y[maxn];
int det(int x1, int y1, int x2, int y2, int x3, int y3) {
return (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1);
}
void solve() {
int ans = 0;
for (int i = 0; i < n; i++) {
int temp = det(x[i], y[i], x[(i + 1) % n], y[(i + 1) % n], x[(i + 2) % n], y[(i + 2) % n]);
if (temp > 0) ans++;
}
printf("%dn", ans);
}
int main() {
scanf("%d", &n);
for (int i = 0; i <= n; i++) scanf("%d %d", &x[i], &y[i]);
solve();
return 0;
}

2.简单数学（也算几何吧）：

这种方法可以说是通用的，不管在哪个叫出发，都可以计算出正确结果。

我们知道对于这个任意三个相邻点都不共线的问题，如果要围成一个闭包，那么最少只要4条边，其余多出来的边一定形成转弯口，而且是指向湖的，而且这样的口计算起来刚好是多余边数的一半，因为毕竟成对出现嘛，所以计算方法就是（假设点数为N）：(N - 4) / 2

代码如下（Accept：15MS / 0KB）：

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int main() {
int N, a, b;
scanf("%d", &N);
for (int i = 0; i <= N; i++) scanf("%d %d", &a, &b);
printf("%dn", (N - 4) / 2);
return 0;
}