c++ - ACM ICPC - 数论

Question

我在练ACM ICPC 历代题http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1030

我无法解决这个问题，完全不知道如何在 3 秒的时间限制内以有效的方式解决问题。我认为这个问题是基于数论的，但不知道该怎么做。谢谢!

Answer 1

虽然转化为 vector 问题，但是三维 vector 和这么多变量还是有些取巧的，所以我们可以先降维，把原方程改成:A[1]* (s[1][2]-s[1][1], s[1][3]-s[1][1]) + a[2]* (s[ 2][2]- s[2][1], s[2][3]- s[2][1]) +.....+a[n]* (s[n][2] - s[n][1],..+a[n]*) = (())。二维 vector 被认为是平面坐标系中以原点为起点的 vector 。如果只有两个 vector ，因为a[i]是一个非负数，所以当只有两个 vector 时，角度一定是PI。如果两个相邻 vector 之间的夹角不大于PI，则N个 vector 可以满足上式。代码不长，但是需要数学思维T_T这是正确的代码。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn=1000+5;
const double PI=acos(-1);
int main()
{
    int n;
    double A[maxn];
    while(scanf("%d",&n),n)
    {
        int s1,s2,s3;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d",&s1,&s2,&s3);
            A[i]=atan2(s2-s1,s3-s1);
        }
        sort(A,A+n);
        double tmp=0;
        for(int i=1;i<n;i++)
            tmp=max(tmp,A[i]-A[i-1]);
        tmp=max(tmp,A[0]-A[n-1]+2*PI);
        if(tmp<=PI)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}