TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2033
  • 题目
  • P2033【CQOI2010】内部白点
    限制 : 时间限制 : 50000 MS   空间限制 : 165536 KB
    问题描述

    无限大正方形网格里有n个黑色的顶点,所有其他顶点都是白色的(网格的顶点即坐标为整数的点,又称整点)。每秒钟,所有内部白点同时变黑,直到不存在内部白点为止。你的任务是统计最后网格中的黑点个数。
      内部白点的定义:一个白色的整点P(x,y)是内部白点当且仅当P在水平线的左边和右边各至少有一个黑点(即存在x1<x<x2使得(x1,y)和(x2,y)都是黑点),且在竖直线的上边和下边各至少有一个黑点(即存在y1<y<y2使得(x,y1)和(x,y2)都是黑点)。

    输入格式

    输入第一行包含一个整数n,即初始黑点个数。以下n行每行包含两个整数(x,y),即一个黑点的坐标。没有两个黑点的坐标相同,坐标的绝对值均不超过10^9。

    输出格式

    输出仅一行,包含黑点的最终数目。如果变色过程永不终止,输出-1。

    样例输入

    4
    0 2
    2 0
    -2 0
    0 -2

    样例输出

    5

    提示

    数据范围
    36%的数据满足:n<=500
    64%的数据满足:n<=30000
    100%的数据满足:n<=100000