526互联

C. Nearest vectors 计算几何

发布时间 2023-09-10 00:39:42作者: 久远寺冇珠

Problem - C - Codeforces

 题意：就如题目所说，从n个向量中，找出两个夹角最小的，输出他们的idx，向量的一个坐标是原点，input中给出了他们的另一个端点的坐标。

做法：先计算出他们与向量（1，0）的夹角，如何算呢？余弦定理，先叉乘后除两向量的长度，得到cos，再用acos函数即可。这里要注意的是，如果遇上了

这种，我们要取的是红色的角，所以判断y如果是个负数，那么就用2pi减去求出的角度。

这里要注意，pi要直接定义

const double pi = acos(-1);

 然后sort后，计算两两差值，再特判一下开头末尾即可。

要注意的是这题卡long double，不开long double 喜提

不卡的话，longdouble还是香的

struct Point{
    long double x, y;
};
long double cal(Point a,Point b){
    long double pot=a.x * b.x + a.y * b.y;
    return acos(pot/sqrt(a.x*a.x+a.y*a.y)/sqrt(a.x*a.x+a.y*a.y));
}
Point op;
void solve(){
    op.x=1.0,op.y=0.0;
    int n;cin>>n;vector<pair<long double,int>>a;
    vector<Point>arr(n+1);
    for(int i=1;i<=n;i++){
        cin>>arr[i].x>>arr[i].y;
        long double temp1=cal(arr[i],op);
        //cout<<i<<" "<<temp1<<" ";
        if(arr[i].y<0.0)temp1=2.0000*pi-temp1;
        a.push_back({temp1,i});
    }
    sort(a.begin(),a.end());
    long double ans=10.0;
    int l=-1,r=-1;
    for(int i=0;i<n-1;i++){
        if((a[i+1].fi-a[i].fi)<ans){
            ans=a[i+1].fi-a[i].fi;
            l=a[i].se,r=a[i+1].se;
        }
    }
    double temp=cal(arr[a[0].se],arr[a[n-1].se]);
    if(temp<ans)cout<<a[0].se<<" "<<a[n-1].se<<"\n";
    else cout<<l<<" "<<r<<"\n";
}