相关链接
题目传送门: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; }
Hi , I do believe this is an excellent blog. I stumbled upon it on Yahoo , i will come back once again. Money and freedom is the best way to change, may you be rich and help other people.
I want meeting utile info, this post has got me even more info! .