https://scg3.piaoztsdy.cn/p/216
考虑依次选取以下 个「关键营地」（需要指出的是，这 个「关键营地」不一定都存在）：
- 号「关键营地」为输入的第一个营地。
- 号「关键营地」为输入的第一个与 号「关键营地」 坐标相同， 坐标不同的营地。
- 号「关键营地」为输入的第一个与 号「关键营地」 坐标不同， 坐标相同的营地。
- 号「关键营地」为输入的第一个与 号「关键营地」 坐标不同， 坐标不同的营地。
- 号「关键营地」为输入的第一个与 号「关键营地」 坐标不同， 坐标不同，与 号「关键营地」 坐标相同， 坐标不同的营地。
- 号「关键营地」为输入的第一个与 号「关键营地」 坐标不同， 坐标不同，与 号「关键营地」 坐标不同， 坐标相同的营地。
- 号「关键营地」为输入的第一个与 号「关键营地」 坐标不同， 坐标不同，与 号「关键营地」 坐标不同， 坐标不同的营地。
可以证明，如果某个询问有解，则这 个「关键营地」中必有一个是该询问的合法解，证明此处从略。
最终的时间复杂度为 ，空间复杂度为 。
#include <bits/stdc++.h>
#include "laser.h"
using namespace std;
int n = 0;
struct Point
{
int x, y, i;
};
Point p[7];
void clear()
{
cout << "";
n = 0;
memset(p, 0, sizeof p);
}
void add(int x, int y)
{
n++;
if (!p[0].i)
{
p[0] = (Point) {x, y, n};
return;
}
if (x == p[0].x && y != p[0].y && !p[1].i) p[1] = (Point) {x, y, n};
if (x != p[0].x && y == p[0].y && !p[2].i) p[2] = (Point) {x, y, n};
if (x != p[0].x && y != p[0].y)
{
if (!p[3].i)
{
p[3] = (Point) {x, y, n};
return;
}
if (x == p[3].x && y != p[3].y && !p[4].i) p[4] = (Point) {x, y, n};
if (x != p[3].x && y == p[3].y && !p[5].i) p[5] = (Point) {x, y, n};
if (x != p[3].x && y != p[3].y && !p[6].i) p[6] = (Point) {x, y, n};
}
}
int query(int x, int y)
{
int ans = n + 1;
for (int i = 0; i <= 6; i++)
if (x != p[i].x && y != p[i].y && p[i].i) ans = min(ans, p[i].i);
if (ans == n + 1) ans = 0;
return ans;
}
int main()
{
cout << "";
start();
}
暂无评论