poj3565 Ants(训练手册例题翻译)

译文:

题目描述

年轻的自然学家Bill正在学院研究蚂蚁,ta研究的蚂蚁以住在苹果树上的一种植物虱为食。每个蚁群都有专属的苹果树。

Bill有一张标注了N个蚁群和N棵苹果树的地图。ta知道蚂蚁在自己的巢穴和捕食点之间行动,都是依靠一种化学物质。这些路线不能互相交叉,否则蚂蚁会搞糊涂,到达错误的领地,从而引发蚁群之间的战争。

Bill想要在蚁群和苹果树之间连线,并且这n条线路(一定是直线)不会互相交叉。在此题目中,一定存在这样的连接方式。你的任务就是编写程序找到这样的连接方式。
这里写图片描述
在这张图片中,蚁群用空心点表示,苹果树用实心点表示,
以上就是一种合法的连接方式。

输入

第一行是一个整数n (1 ≤ n ≤ 100) —苹果树和蚁群的数量 。之后是n行,每行描述一个蚁群的位置,之后又是n行,用来描述苹果树的位置。每棵苹果树和每个蚁群都是用两个整数x,y来描述位于笛卡尔坐标系中的坐标 (−10 000 ≤ x, y ≤ 10 000) 所有的蚁群和苹果树在平面上坐标相异。没有三个点在同一条线上。

输出

输出n行,每行一个整数。第i行(i=1~n)的整数表示第i个蚁群个哪棵苹果树相连

样例输入
5
-42 58
44 86
7 28
99 34
-13 -59
-47 -44
86 74
68 -75
-68 60
99 -60

样例输出
4
2
1
5
3

原文:

Description

Young naturalist Bill studies ants in school. His ants feed on plant-louses that live on apple trees. Each ant colony needs its own apple tree to feed itself.

Bill has a map with coordinates of n ant colonies and n apple trees. He knows that ants travel from their colony to their feeding places and back using chemically tagged routes. The routes cannot intersect each other or ants will get confused and get to the wrong colony or tree, thus spurring a war between colonies.

Bill would like to connect each ant colony to a single apple tree so that all n routes are non-intersecting straight lines. In this problem such connection is always possible. Your task is to write a program that finds such connection.
这里写图片描述
On this picture ant colonies are denoted by empty circles and apple trees are denoted by filled circles. One possible connection is denoted by lines.

Input

The first line of the input file contains a single integer number n (1 ≤ n ≤ 100) — the number of ant colonies and apple trees. It is followed by n lines describing n ant colonies, followed by n lines describing n apple trees. Each ant colony and apple tree is described by a pair of integer coordinates x and y (−10 000 ≤ x, y ≤ 10 000) on a Cartesian plane. All ant colonies and apple trees occupy distinct points on a plane. No three points are on the same line.

Output

Write to the output file n lines with one integer number on each line. The number written on i-th line denotes the number (from 1 to n) of the apple tree that is connected to the i-th ant colony.

Sample Input
5
-42 58
44 86
7 28
99 34
-13 -59
-47 -44
86 74
68 -75
-68 60
99 -60

Sample Output
4
2
1
5
3

原文地址:https://www.cnblogs.com/wutongtong3117/p/7673106.html