题目描述
给定平面上 \(n\) 个点，从 \(1\) 号点出发，一开始朝向 \(2\) 号点，每次只能顺时针转 \([0^{\circ},180^{\circ}]\) 后前进到某个点，要求走一条每条边都不交（除了在端点处）路径，最后回到 \(1\) ，求最多能走过多少个不是 \(1\) 的点。
\(1 \leq n \leq 1000\) 。
这是一道计算几何题。
手模容易发现，如果你旋转的总角度超过了 \(360^{\circ}\) ，那么无论如何你都不能回到 \(1\) 点。所以要求就是只能顺时针转且总角度不超 \(360^{\circ}\) 。这启发我们以 \(1\) 号点为原点，以 \(2\) 号点为 \(0\) 度线对其他点进行极角排序，按照这个顺序计算（前面的一定不会依赖后面的）。
我们假设 \(f_{i,j}\) 为现在到点 \(i\) ，上一个是点 \(j\) 的最大点数，枚举前驱 \(k\) ，纸上手模发现合法条件是 \(k \to j\) 在 \(j \to i\) 的左边，也就是 \((j \to i) \otimes (k \to j)\) （外积）要大于 \(0\) 。
这样是 \(\Theta(n^3)\) 的。
我们观察状态，发现同样是走过 \(j\) 个点，点 \(i\) 的前驱一定越 “左” 越好，也就是取所有前驱到 \(i\) 中向量，顺时针方向第一个，这样可以取到后面更多的点，如图，取 \(k\) 一定是最优的。
下面假设 “前驱” 就是上文说的最优的前驱。
前驱具有一定的单调性：假设现在在 \(i\) ，走过 \(j + 1\) 个点的前驱 \(k\) ，走过 \(j\) 个点的前驱 \(r\) ，一定满足 \(r \to i\) 在 \(k \to i\) 的左边，不然用 \(k\) 就会严格优于 \(r\) 。
所以，我们可以利用这个二分。
设 \(f_{i,j}\) 表示在 \(i\) ，已经走过 \(j\) 个点的最优前驱，每次枚举 \(i\) 和转移点 \(k\) ，二分得到最大的 \(j\) 使得 \(f_{k,j} \to k\) 可以转到 \(k \to i\) ，用 \(k\) 更新 \(f_{i,j + 1}\) ，注意当 \(f_{i,j + 1}\) 有值时要比较一下。
然后对于 \(i\) ，将 \(f_{i,j}\) 与 \(f_{i,j + 1}\) 取更优的一个即可。
时间复杂度 \(\Theta(n^2\log n)\) 。
现在具体讲一下如何以一个点为原点，一个点为零点极角排序。
首先我们将所有点的坐标减去 \(1\) 的坐标，这样相对位置不变。
观察 atan2 函数的值，发现是这样的：
我们想要一个从 \(x\) 正半轴开始，递增直到一圈的效果，所以分类：
-
如果 atan2 为负数，则变成相反数。
-
否则变成 \(2 \pi - atan2\) 。
这样就得到了一个从 \(x\) 正半轴开始递增的函数。
我们又想要它以 \(2\) 号点为零轴，直接将 atan2 减去 atan2(y2,x2) 后，跨过零点的值会出现问题，所以如果小于零，则加上 \(2\pi\) 即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
typedef long double ld;
const ld PI = 3.141592653589793239;
struct Point{
ld x,y,theta;
}a[N];
#define Vector Point
Vector operator -(Point p,Point q)
{
return Vector{q.x - p.x,q.y - p.y};
}
ld operator *(Vector p,Vector q)
{
return p.x * q.y - p.y * q.x;
}
ld getan(ld y,ld x)
{
ld ret = atan2(y,x);
if(ret < 0) ret = -ret;
else ret = 2 * PI - ret;
return ret;
}
inline bool onleft(Vector p,Vector q) // p on the left of q?
{
return (q * p >= 0);
}
int f[N][N],n;
int main()
{
cin>>n;
for(int i = 1;i <= n;i++) cin>>a[i].x>>a[i].y;
for(int i = 2;i <= n;i++) a[i].x -= a[1].x,a[i].y -= a[1].y;
a[1].x = a[1].y = 0.00;
for(int i = 2;i <= n;i++) a[i].theta = (getan(a[i].y,a[i].x) - getan(a[2].y,a[2].x));
for(int i = 3;i <= n;i++) if(a[i].theta < 0) a[i].theta += PI * 2;
sort(a + 3,a + n + 1,[&](Point p,Point q) {return p.theta < q.theta;});
for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) f[i][j] = -1;
f[2][1] = 1;
int ans = 2;
for(int i = 3;i <= n;i++)
{
for(int j = 2;j < i;j++)
{
if(!onleft(a[i] - a[j],a[1] - a[j])) continue;
int l = 0,r = i - 2;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(f[j][mid] == -1) r = mid - 1;
else
{
if(onleft(a[j] - a[f[j][mid]],a[i] - a[j])) l = mid;
else r = mid - 1;
}
}
if(l == 0) continue;
if(f[i][l + 1] == -1) f[i][l + 1] = j;
else
{
if(onleft(a[i] - a[j],a[i] - a[f[i][l + 1]]))
f[i][l + 1] = j;
}
ans = max(ans,l + 1);
}
for(int j = i - 1;j >= 1;j--)
{
if(f[i][j] == -1) f[i][j] = f[i][j + 1];
else if(f[i][j + 1] != -1)
{
if(onleft(a[i] - a[f[i][j + 1]],a[i] - a[f[i][j]]))
f[i][j] = f[i][j + 1];
}
}
}
cout<<ans;
return 0;
}