[计算几何]cf598C Nearest vectors

一个简单的极角排序

题意

给n个从原点出发的向量,求夹角最小的两个向量
数据范围:2 ≤ n ≤ 100 000,|x|,|y| ≤ 10 000, x_2 + y_2 > 0
我是题目链接

样例

input
4
-1 0
0 -1
1 0
1 1

output
3 4

input
6
-1 0
0 -1
1 0
1 1
-4 -5
-4 -6

output
6 5

题解

他就是个很简单的极角排序,奈何写不出来。。。
看过大佬的题解后恍然大悟
我太菜了
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
const long double pi=acos(-1);

struct node{
int x,y,id;
long double deg;
friend bool operator < (const node &a,const node &b){
return a.deg<b.deg;
}
}p[maxn];

long double atann(int y,int x){
long double t=atan2(y,x);
if(t<0) t+=pi*2;
return t;
}


int main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
scanf("%d%d",&p[i].x,&p[i].y);
p[i].deg=atann(p[i].y,p[i].x);
p[i].id=i;
}
sort(p+1,p+n+1);
p[0].deg=p[n].deg-pi*2;
p[0].id=p[n].id;
int qwq;
long double ans=4*pi;
for(int i=1;i<=n;i++){
if(p[i].deg-p[i-1].deg<ans){
ans=p[i].deg-p[i-1].deg;
qwq=i;
}
}
printf("%d %d\n",p[qwq].id,p[qwq-1].id);
return 0;
}