「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$是否在三角形内部即可，可以使用叉积判别。

注意实现细节。

---

代码

#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];
				}
		}
}