隐藏
「UTR 3」几何冲刺 - 极角排序+叉积 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「UTR 3」几何冲刺 - 极角排序+叉积

题目大意

    Scape非常喜欢在和Mythological逛公园的时候,讲时间复杂度的知识给她听。但是他很快便伤心地发现Mythological对复杂度的兴趣,还没有旁边的蚯蚓列队表演的兴趣高,只好向whx诉苦。
    whx面对Scape的疑惑,告诉他,重要的是Mythological喜欢什么,而不是他自己喜欢什么。Scape发现Mythological特别喜欢玩Geometry Dash,所以特意下载了一个来玩。
    打开游戏,Scape发现平面直角坐标系上有$n$个红点$P_0,P_1,\ldots,P_{n−1}$和$m$个蓝点$Q_0,Q_1,\cdots,Q_{m−1}$。(其中这$n+m$个点和原点$O$一共$n+m+1$个点中,任意三点不共线。)
    Scape很快反应过来,以原点$O$和任意两个红点$P_i,P_j$为顶点构成的三角形$OP_iP_j$一共有$\frac{n(n−1)}2$个。
    如果一个三角形的内部不包含任何蓝点,Scape称该三角形是空的,否则,Scape称该三角形是非空的。
    Scape的任务是判断以原点和任意两个红点为顶点构成的$\frac{n(n−1)}2$个三角形中,每个三角形是空的还是非空的。为了证明一个三角形非空,对于每个非空的三角形,请给出任意一个在该三角形内部的蓝点$Q_k$($0\le k\lt m$)。

传送门


题目分析

官方题解

发现只需要求出一个合法的蓝点即可。
对给出的点进行极角排序,枚举$P_i$,从$P_{i+1}$开始扫描点$P_j$,构成三角形$\triangle OP_iP_j$,记录扫描过程中$\angle XP_iO$最小的蓝点$X$,判断最小的蓝点$X$是否在三角形内部即可,可以使用叉积判别。

注意实现细节。


代码

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include "triangles.h"
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

const double pi=acos(-1);

struct Point {
double x,y,angle;
int id;
bool type;
Point(double _x=0,double _y=0,int i=0,bool t=0):x(_x),y(_y),id(i),type(t) {
angle=atan2(y,x);
}
Point operator - (const Point& b) const {
return Point(b.x-x,b.y-y);
}
bool operator < (const Point& b) const {
return angle<b.angle;
}
};

typedef Point Vector;

double Cross(Vector a,Vector b) {
return a.x*b.y-b.x*a.y;
}

vector<Point> p;

void check_triangles(int n, int m, int *rx, int *ry, int *bx, int *by, int **result) {
for(int i=0; i<n; i++)p.push_back(Point(rx[i],ry[i],i,0));
for(int i=0; i<m; i++)p.push_back(Point(bx[i],by[i],i,1));
sort(p.begin(),p.end());
int cnt=p.size();
for(int i=0; i<cnt; i++) {
Point now=p[i];
now.angle+=2*pi;
p.push_back(now);
}
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
result[i][j]=-1;
for(int i=0; i<cnt; i++)
if(p[i].type==0) {
Point last;
bool found=0;
for(int j=i+1; j<2*cnt&&p[j].angle-p[i].angle<pi; j++)
if(p[j].type==0&&found) {
int x=p[i].id,y=p[j].id;
if(x>y)swap(x,y);
if(Cross(last-p[i],last-p[j])>0)result[x][y]=last.id;
} else if(p[j].type==1&&(!found||Cross(last-p[i],last-p[j])<0)) {
found=1;
last=p[j];
}
}
}
姥爷们赏瓶冰阔落吧~