A11742 | Guard Duty (hard)
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Now that Heidi knows that she can assign Rebel spaceships to bases (recall the easy subtask), she is asking you: how exactly to do this? Now, given positions of $N$ spaceships and $N$ bases on a plane, your task is to connect spaceships and bases with line segments so that:
- The segments do not intersect.
- Such a connection forms a perfect matching.
- The segments do not intersect.
- Such a connection forms a perfect matching.
输入格式
The first line contains an integer $N$ ( $1<=n<=10000$ ). For $1<=i<=N$ , the $i+1$ -th line contains two integers $x_{i}$ and $y_{i}$ ( $|x_{i}|,|y_{i}|<=10000$ ) denoting the coordinates of the $i$ -th spaceship. The following $N$ lines have the same format, denoting the position of bases. It is guaranteed that no two points coincide and no three points are on the same line.
输出格式
The output should have $N$ lines. The $i$ -th line should contain an integer $p_{i}$ , the index of the base to which the $i$ -th spaceship is connected. The sequence $p_{1},...,p_{N}$ should form a permutation of $1,...,N$ .
It is guaranteed that a solution exists. If there are multiple solutions, you can output any one of them.
It is guaranteed that a solution exists. If there are multiple solutions, you can output any one of them.
输入输出样例
输入 #1
4 6 6 5 1 2 4 4 0 5 4 1 2 2 1 3 5
输出 #1
4 1 2 3
输入 #2
3 6 6 3 4 2 5 1
输出 #2
3
输入 #3
4 12 15 7 4 19 3 30 14 1 5 23 17 25
输出 #3
6
In the first example, there are five valid schedules: $[1,4],[6,7]$ with total time 4, $[1,4],[6,12]$ with total time 9, $[1,4],[7,12]$ with total time 8, $[1,6],[7,12]$ with total time 10, and $[4,6],[7,12]$ with total time 7. So the answer is 4.
In the second example, there is only 1 valid schedule: $[1,2],[3,4],[5,6]$ .
For the third example, one possible schedule with total time 6 is: $[1,3],[4,5],[14,15],[23,25]$ .
In the second example, there is only 1 valid schedule: $[1,2],[3,4],[5,6]$ .
For the third example, one possible schedule with total time 6 is: $[1,3],[4,5],[14,15],[23,25]$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted