2023级算法C5上机赛

2023级算法C5上级赛

考察方向

计算几何

A 三点共线

这题本来是一道非常简单的题目，但是被我犯了一个重要错误，后面影响到了我的整个上机心态，不得不说一个小错误变成了一个严重错误，希望同学朋友能以我为鉴orz

具体思路很简单，我们想要对n个点判断是否存在不共线的三个点，其实只需要以前两个点（之所以取前两个是因为每组数据必然有这两个点而且简单，当然取其它也可以）所在直线为基准判断是否与这两个点共线。

接下来可以看一段错误代码，了解一下为什么能错

#include<bits/stdc++.h>
#define N 100001
using namespace std;

struct Point {
    long long x;
    long long y;
};

// p1p2 x p1p3
long long cross_product(Point p1, Point p2, Point p3) {
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        Point p1, p2, p3;
        scanf("%lld%lld", &p1.x, &p1.y);
        scanf("%lld%lld", &p2.x, &p2.y);
        bool has = false;
        for (int i = 3; i <= n; i++) {
            scanf("%lld%lld", &p3.x, &p3.y);
            if (cross_product(p1, p2, p3) != 0) {
                has = true;
                break;
            }
        }
        if (has) {
            printf("how?\n");
        } else {
            printf("boo how! boo how!\n");
        }
    }
    return 0;
}

乍一眼看上去思路好像没大问题，但是注意到，因为在同一个测试中存在多组数据，多组数据的数据输入输出一定要注意不要相互影响，这段代码最大错误就是它判断到存在不共线的点后提前暂停了，导致上一个数据点的数据被遗传到了下一个点继续使用，造成错误。