codeforces 996 E. Leaving the Bar

題目：點選打開連結

題意：給定一些向量，你可以改變它的符号，使得這些向量之和的長度小于1.5e6。

分析：注意有方向，可以将速度分解成為x，y軸方向上的分量，每次貪心取最小，因為每次我貪心原則是一樣的，最後的結果有可能大于1.5e6 ，我們需要加一些随機性,，多次貪心，直到結果滿足題意。正解是每三個向量中都能找到兩個向量合起來 <= 1e6，然後不斷合并，最後隻會剩下一個或者兩個向量，如果一個向量肯定 <= 1e6， 如果是兩個向量一定 <= 1.5 * 1e6。

代碼：

#pragma comment(linker, "/STACK:102400000,102400000")///手動擴棧
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<set>
#include<map>
using namespace std;
#define debug test
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f
#define eps 1e-10
#define MOD 1000000007
#define PI acos(-1.0)
const int N = 3e5+10;
const ll pp = 1500000;

ll gcd(ll p,ll q)
{
    return q==0?p:gcd(q,p%q);
}
int to[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};

int n;

struct nd
{
    ll x,y;
    int id;
} p[N];

int a[N];

ll d(ll a,ll b)
{
    return a*a+b*b;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>p[i].x>>p[i].y;
        p[i].id=i;
    }
    while(1)
    {
        random_shuffle(p+1,p+n+1);
        ll x=0,y=0;
        for(int i=1; i<=n; i++)
        {
            if(d(x-p[i].x,y-p[i].y)<d(x+p[i].x,y+p[i].y))
            {
                x-=p[i].x,y-=p[i].y;
                a[p[i].id]=-1;
            }
            else
            {
                x+=p[i].x,y+=p[i].y;
                a[p[i].id]=1;
            }
        }
        if(x*x+y*y<=pp*pp)
        {
            for(int i=1; i<=n; i++)
            {
                cout<<a[i];
                if(i!=n) cout<<" ";
            }
            break;
        }
    }
    return 0;
}