CF390A.Inna and Alarm Clock
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Inna loves sleeping very much, so she needs n alarm clocks in total to wake up. Let's suppose that Inna's room is a 100 × 100 square with the lower left corner at point (0, 0) and with the upper right corner at point (100, 100). Then the alarm clocks are points with integer coordinates in this square.
The morning has come. All n alarm clocks in Inna's room are ringing, so Inna wants to turn them off. For that Inna has come up with an amusing game:
- First Inna chooses a type of segments that she will use throughout the game. The segments can be either vertical or horizontal.
- Then Inna makes multiple moves. In a single move, Inna can paint a segment of any length on the plane, she chooses its type at the beginning of the game (either vertical or horizontal), then all alarm clocks that are on this segment switch off. The game ends when all the alarm clocks are switched off.
Inna is very sleepy, so she wants to get through the alarm clocks as soon as possible. Help her, find the minimum number of moves in the game that she needs to turn off all the alarm clocks!
因娜非常喜欢睡觉,因此她总共需要 n 个闹钟来叫醒自己。假设因娜的房间是一个边长为 100 的正方形,其左下角位于点 (0,0),右上角位于点 (100,100)。那么这些闹钟就是该正方形内具有整数坐标的点。
清晨已至。因娜房间内的全部 n 个闹钟都在响,因此她想将它们全部关闭。为此,因娜设计了一个有趣的游戏:
- 首先,因娜选定一种线段类型,并在整局游戏中始终使用该类型。线段只能是竖直的或水平的。
- 然后,因娜进行若干次操作。在单次操作中,因娜可以在平面上绘制一条任意长度的线段(其方向类型已在游戏开始时选定:要么全为竖直线段,要么全为水平线段),所有位于该线段上的闹钟都会被关闭。当所有闹钟均被关闭时,游戏结束。
因娜非常困倦,因此她希望尽快完成这一过程。请帮帮她,求出她关掉所有闹钟所需的最少操作次数!
输入格式
The first line of the input contains integer n (1 ≤ n ≤ 105) — the number of the alarm clocks. The next n lines describe the clocks: the i-th line contains two integers x__i, y__i — the coordinates of the i-th alarm clock (0 ≤ x__i, y__i ≤ 100).
Note that a single point in the room can contain any number of alarm clocks and the alarm clocks can lie on the sides of the square that represents the room.
输入的第一行包含一个整数 n(1 ≤ n ≤ 105)—— 表示闹钟的数量。接下来的 n 行描述这些闹钟:第 i 行包含两个整数 xi、yi —— 表示第 i 个闹钟的坐标(0 ≤ xi,yi ≤ 100)。
注意:房间内的同一个点上可以放置任意数量的闹钟,且闹钟可以位于表示房间的正方形的边上。
输出格式
In a single line print a single integer — the minimum number of segments Inna will have to draw if she acts optimally.
在一行中输出一个整数——即伊娜在最优策略下需要绘制的最少线段数。
输入输出样例
输入#1
4 0 0 0 1 0 2 1 0
输出#1
2
输入#2
4 0 0 0 1 1 0 1 1
输出#2
2
输入#3
4 1 1 1 2 2 3 3 3
输出#3
3
说明/提示
In the first sample, Inna first chooses type "vertical segments", and then she makes segments with ends at : (0, 0), (0, 2); and, for example, (1, 0), (1, 1). If she paints horizontal segments, she will need at least 3 segments.
In the third sample it is important to note that Inna doesn't have the right to change the type of the segments during the game. That's why she will need 3 horizontal or 3 vertical segments to end the game.
在第一个样例中,Inna 首先选择“竖直线段”类型,然后她画出端点分别为 (0,0)、(0,2) 的线段;以及例如端点为 (1,0)、(1,1) 的线段。如果她绘制水平线段,则至少需要 3 条线段。
在第三个样例中,需要注意的是:Inna 在游戏过程中无权更改线段的类型。因此,她必须使用 3 条水平线段或 3 条竖直线段才能结束游戏。
输入解题思路,AI测评打分。不知道怎么写?