Skip to content

11561: 【原1561】最小覆盖

题目

题目描述

author: ACM Regional Taiwan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1561

Description

第一象限中有一些整点(数据保证不在x轴或y轴上),现在要求用如下两种曲线将它们覆盖住:

  • \(x^2 + y^2 = k, k \in N\)
  • \(y = kx, k \in R\)

求最少需要多少条曲线才能将所有这些点覆盖。

Input Format

第一行共一个整数n表示整点的个数。

第二行到第n+1,每行两个整数,表示第i个整点的坐标(整点可能重叠)

Output Format

输出一个整数m,表示至少多少条曲线能覆盖所有的点。

Sample Input

3
5 5
7 1
10 10

Sample Output

2

HINT

对于100%的数据,所有的整点坐标都在long long范围内。

对于40%的数据,n <= 1000。

对于100%的数据,n <= 200000。

对于70%的数据,整点的坐标范围在[1, 1e6]之间。

注意边的储存方式。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!