【日常小测】route

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/07/20170624_problem.pdf

解题报告

我们往后多看一步:

假设下一步我们需要向左走,那么我们这一步就走到对于现在所在的点极角序最小的点去
否则就走到极角序最大的点去

不难发现这样一定能构造出一组解

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5009;

int n, vis[N];
char cmd[N];
struct Point{
	int x, y;
	inline Point() {
	}
	inline Point(int a, int b):x(a), y(b) {
	}
	inline Point operator - (const Point &P) {
		return Point(x - P.x, y - P.y);
	}
	inline bool operator < (const Point &P) {
		return x < P.x || (x == P.x && y < P.y);
	}
	inline LL operator * (const Point &P) {
		return x * P.y - y * P.x;
	}
}p[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void solve(int w, int stp) {
	vis[w] = 1;
	printf("%d ", w);
	if (stp < n) {
		int nxt = 0;
		for (int i = 1; i <= n; i++) {
			if (!vis[i]) {
				if (!nxt || (cmd[stp] == 'L'? (p[nxt] - p[w]) * (p[i] - p[w]) < 0: (p[nxt] - p[w]) * (p[i] - p[w]) > 0)) {
					nxt = i;
				}
			}
		}
		solve(nxt, stp + 1);
	}
}

int main() {
	freopen("route.in", "r", stdin);
	freopen("route.out", "w", stdout);
	n = read();
	int s = 0;
	for (int i = 1; i <= n; i++) {
		p[i].x = read();
		p[i].y = read();
		if (!s || p[i] < p[s]) {
			s = i;
		}
	}
	scanf("%s", cmd);
	solve(s, 1);
	return 0;
}

【日常小测】通技进阶

相关链接

题目传送门:http://paste.ubuntu.com/23686161/

解题报告

这题好神啊!

首先这题是三维几何,大家都不是很会的样子
于是我们考虑用一个平行于y-z平面的平面A,沿着x轴扫描
于是三维的直线就变成了一个在二维平面上运动的点

现在考虑那个两两相交的边集
选定一个点为原点进行坐标变换后,其他点只会有两种情况:

  1. 同时经过原点
  2. 都在同一条经过原点的直线上以不同速度运动

于是暴力枚举那个点,然后sort之后搞一搞
在 \(O(nlogn)\) 的时间复杂度内就可以解决啦!

Code

#include<bits/stdc++.h>
#define LL long long
#define Vector Point
using namespace std;

const int N = 2000+9;
const double EPS = 1e-8;
const double STP = 1e3;
const double PI = acos(-1);

int n,vout;
double te[N];
struct Point{
	double x,y;
	inline Point() {}
	inline Point(double _x, double _y):x(_x),y(_y) {}
	inline Point operator + (const Point &B) {return Point(x+B.x, y+B.y);}
	inline Point operator - (const Point &B) {return Point(x-B.x, y-B.y);}
	inline Point operator * (const double a) {return Point(x*a, y*a);}
	inline Point operator / (const double a) {return Point(x/a, y/a);}
	inline double operator * (const Point &B) {return x*B.x + y*B.y;}
	inline double operator ^ (const Point &B) {return x*B.y - y*B.x;}
	inline double operator / (const Point &B) {if(abs(x)>EPS)return x/B.x; else return y/B.y;}
	inline double len() {return sqrt(x*x + y*y);}
}ori[N],sta[N],spd[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int solve(double *arr, int tot) {
	sort(arr+1, arr+1+tot);
	int ret = 0;
	for (int l=1,r;l<=tot;l=r+1) {
		for (r=l;r<tot&&abs(arr[l]-arr[r+1])<EPS;r++);
		ret = max(r - l + 1, ret);
	}
	return ret;
}

inline bool cmp(const Vector &A, const Vector &B) {
	if (abs(A.x-B.x)<EPS) return A.y < B.y;
	return A.x < B.x;
}

inline int solve(Vector *arr, int tot) {
	sort(arr+1, arr+1+tot, cmp);
	int ret = 0;
	for (int l=1,r,mx=0;l<=tot;l=r+1,mx=0) {
		for (r=l;r<tot&&abs(arr[l].x-arr[r+1].x)<EPS;r++);
		for (int i=l+1;i<=r;i++) if (abs(arr[i].y-arr[i-1].y)<EPS) mx++;
		ret = max(ret, r - l + 1 - mx);
	}
	return ret;
}

int main() {
	freopen("gentech.in","r",stdin);
	freopen("gentech.out","w",stdout);
	n = read();
	for (int i=1;i<=n;i++) {
		double x1,x2; Point p1,p2;
		x1 = read(); p1.x = read(); p1.y = read();
		x2 = read(); p2.x = read(); p2.y = read();
		ori[i] = (p1 - p2) / (x1 - x2) * STP;
		sta[i] = (p1 - p2) / (x1 - x2) * (STP - x1) + p1;
	}
	for (int k=1,tot=0;k<=n;k++,tot=0) {
		for (int i=1;i<=n;i++) {
			if (i != k) {
				Point bas = sta[i] - sta[k];
				Vector cur = ori[i] - ori[k];
				if (abs(bas ^ cur) < EPS) {
					te[++tot] = bas / cur;
					spd[tot].x = atan2(cur.y, cur.x);
					spd[tot].y = cur.len();
				}
			}
		}
		vout = max(vout, solve(te, tot));
		vout = max(vout, solve(spd, tot));
	}
	printf("%d\n",vout+1);
	return 0;
}