#PQJ66x10763. QOJ 66_10763

    ID: 3021 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:ZJOI 2012枚举

QOJ 66_10763

小蓝的好友(mrx) 【题目描述】 终于到达了这次选拔赛的最后一题,想必你已经厌倦了小蓝和小白的故事, 为了回馈各位比赛选手,此题的主角是贯穿这次比赛的关键人物——小蓝的好 友。 在帮小蓝确定了旅游路线后,小蓝的好友也不会浪费这个难得的暑假。与小 蓝不同,小蓝的好友并不想将时间花在旅游上,而是盯上了最近发行的即时战略 游戏——SangoCraft。但在前往通关之路的道路上,一个小游戏挡住了小蓝的好 友的步伐。 “国家的战争其本质是抢夺资源的战争”是整款游戏的核心理念,这个小游 戏也不例外。简单来说,用户需要在给定的长方形土地上选出一块子矩形,而系 统随机生成了N 个资源点,位于用户所选的长方形土地上的资源点越多,给予 用户的奖励也越多。悲剧的是,小蓝的好友虽然拥有着极其优秀的能力,但同时 也有着极差的RP,小蓝的好友所选的区域总是没有一个资源点。 终于有一天,小蓝的好友决定投诉这款游戏的制造厂商,为了搜集证据,小 蓝的好友想算出至少包含一个资源点的区域的数量。作为小蓝的好友,这自然是 你分内之事。

【输入说明】 每个输入文件中仅包含一个测试数据。 第一行包含两个由空格隔开的正整数R,C,N,表示游戏在一块[1,R]X[1,C]的 地图上生成了N 个资源点。 接下来有N 行,每行包含两个整数 x,y,表示这个资源点的坐标 ( )。 【输出说明】 输出文件应仅包含一个整数,表示至少包含一个资源点的区域的数量。具 体的说,设N 个资源点的坐标为 (i=1..n),你需要计算有多少个四元组

(LB,DB,RB,UB)满足 ,且存在一个i 使得 均成立。 【样例输入】 5 5 4 1 2 2 3 3 5 4 1 【样例输出】 139 【数据范围】 对于20%的数据,

对于40%的数据,

对于100%的数据, ,资源点的位置两两不同,且 位置为随机生成。