## 【日常小测】route

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

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);
int s = 0;
for (int i = 1; i <= n; i++) {
if (!s || p[i] < p[s]) {
s = i;
}
}
scanf("%s", cmd);
solve(s, 1);
return 0;
}


## 【日常小测】通技进阶

### 解题报告

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

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

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);
for (int i=1;i<=n;i++) {
double x1,x2; Point p1,p2;
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;
}