题目
平面上有若干个点,一只蚂蚁走路不能向右转,问最多能经过多少个点。
蚂蚁的起点为 ( 0 , m i n ( y i ) ) (0,min(y_i)) (0,min(yi))
求解
凸包变形,路径一定是下凸壳、上凸壳、下凸壳、上凸壳…组成的,循环找凸壳即可。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2e5 + 5;
typedef struct Point
{
int id;
double x, y;
Point operator-(const Point &temp) const
{
Point T;
T.x = x - temp.x;
T.y = y - temp.y;
return T;
// return Point{1, x - temp.x, y - temp.y};
}
bool operator<(const Point &temp) const
{
if (x == temp.x)
return y > temp.y;
return x < temp.x;
}
} Vector;
Point p[N];
int stk[N];
bool vis[N];
double cross(Vector A, Vector B)
{
return A.x * B.y - A.y * B.x;
}
void solve()
{
int n;
scanf("%d", &n);
p[0].x = 0;
p[0].y = 0x3f3f3f3f;
for (int i = 1; i <= n; i++)
{
cin >> p[i].id;
scanf("%lf %lf", &p[i].x, &p[i].y);
p[0].y = min(p[0].y, p[i].y);
}
sort(p + 1, p + 1 + n);
int top = 0, op = 1;
memset(vis, 0, sizeof vis);
bool flag = 1;
stk[++top] = 0; //先压入起点
while (flag)
{
flag = 0;
if (op)
for (int i = 1; i <= n; i++)
{
if (vis[i])
continue;
while (top >= 2 && cross(p[stk[top]] - p[stk[top - 1]], p[i] - p[stk[top - 1]]) <= 0)
vis[stk[top--]] = 0;
flag = 1;
stk[++top] = i;
vis[i] = 1;
}
else
for (int i = n; i >= 1; i--)
{
if (vis[i])
continue;
while (top >= 2 && cross(p[stk[top]] - p[stk[top - 1]], p[i] - p[stk[top - 1]]) <= 0)
vis[stk[top--]] = 0;
flag = 1;
stk[++top] = i;
vis[i] = 1;
}
op ^= 1;
}
cout << top - 1 << ' ';
for (int i = 2; i <= top; i++)
printf("%d ", p[stk[i]].id);
puts("");
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}