UVA 10089 Repackaging 數學問題，10089repackaging

UVA 10089 Repackaging 數學問題，10089repackaging

大致題意：給出幾個包裹，每個包裹都包裝好了3種大小的杯子。現在要重新包裝，使向量

a[1]*(s[1][1],s[1][2],s[1][3])+a[2]*(s[2][1],s[2][2],s[2][3])+.....+a[n]*(s[n][1],s[n][2],s[n][3])=(k,k,k). 就這樣轉化成了向量問題其中a[i]為非負整數，k為正整數。

雖然轉化成了向量問題，但是三維向量和這麼多變量有點棘手，所以我們可以先降維，將原等式變化成：

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],s[n][3]- s[n][1])=(0,0).

把二維向量看成以平面坐標系中以原點為起點的向量。如果只有兩個向量，因為a[i]為非負數，所以只有兩個向量的時候夾角必須為PI。n個向量的話，只要相鄰兩個向量的夾角不大於PI即可滿足上述等式。代碼不長，但是需要數學思維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;
}