计算几何,向量——cf995c

网上的题解直接用随机过的，

自己用模拟就模拟三个向量的和并就模拟不出来。。

以后再回头看看

#include<bits/stdc++.h>

#include<cmath>

using namespace std;

const double esp = 1e-;

const int maxn = 1e5+;

const double C = 180.0/acos(-1.0);

struct Vector{

    double x,y,len,angle;

    int k,id;

}p[maxn];

int cmp(Vector a,Vector b){return a.len>b.len;}

int n;

void reverse(Vector &v){

    v.k*=-;v.x*=-;v.y*=-;

    v.angle=atan2(v.y,v.x)*C;

    if(v.angle<)v.angle+=;

}

void add(Vector &a, Vector &b){

    a.x+=b.x;a.y+=b.y;

    a.len=sqrt(a.x*a.x+a.y*a.y);

    a.angle=atan2(a.y,a.x)*C;

    if(a.angle<)a.angle+=;

}

void Merge(Vector &a,Vector &b,Vector &c){//把c向量加到a向量或者b向量里

    double r1=a.angle,r2=c.angle;

    if(r1>r2)swap(r1,r2);

    double A=min(fabs(r2-r1),fabs(r1-r2+));

    if(A<= && A>=){//形成钝角

        add(a,c);return;

    }

    else if(A<=){//形成锐角

        reverse(c);

        add(a,c);

        return;

    }

    r1=b.angle,r2=c.angle;

    if(r1>r2)swap(r1,r2);

    double B=min(fabs(r2-r1),fabs(r1-r2+));

    if(B<= && B>=){

        add(b,c);return;

    }

    else if(B<=){//形成锐角

        reverse(c);

        add(b,c);

        return;

    }

    Vector tmp=b;b=c;c=tmp;

    r1=a.angle,r2=c.angle;

    if(r1>r2)swap(r1,r2);

    A=min(fabs(r2-r1),fabs(r1-r2+));

    if(A<= && A>=){//形成钝角

        add(a,c);return;

    }

    else if(A<=){//形成锐角

        reverse(c);

        add(a,c);

        return;

    }

}

int main(){

    cin>>n;

    for(int i=;i<=n;i++){

        scanf("%lf%lf",&p[i].x,&p[i].y);

        p[i].len=sqrt(p[i].x*p[i].x+p[i].y*p[i].y);

        p[i].angle=atan2(p[i].y,p[i].x)*C;

        if(p[i].angle<)

            p[i].angle+=;

        p[i].id=i;p[i].k=;

    }

    sort(p+,p++n,cmp);

    Vector &a=p[], &b=p[];

    for(int i=;i<=n;i++){

        Vector &c=p[i];

        Merge(a,b,c);

        if((a.x+b.x)*(a.x+b.x)>=2.25*1e12)

            cout<<i<<" NO";

    }

    /*

cout<<a.x<<" "<<a.y<<'\n';

cout<<b.x<<" "<<b.y<<'\n';*/

    int ans[maxn]={};

    for(int i=;i<=n;i++)

        ans[p[i].id]=p[i].k;

    for(int i=;i<=n;i++)cout<<ans[i]<<" ";

}