cccc初赛 L3-003 长城
L3-009. 长城
正如我们所知,中国古代长城的建造是为了抵御外敌入侵。在长城上,建造了许多烽火台。每个烽火台都监视着一个特定的地区范围。一旦某个地区有外敌入侵,值守在对应烽火台上的士兵就会将敌情通报给周围的烽火台,并迅速接力地传递到总部。
现在如图1所示,若水平为南北方向、垂直为海拔高度方向,假设长城就是依次相联的一系列线段,而且在此范围内的任一垂直线与这些线段有且仅有唯一的交点。
图 1
进一步地,假设烽火台只能建造在线段的端点处。我们认为烽火台本身是没有高度的,每个烽火台只负责向北方(图1中向左)瞭望,而且一旦有外敌入侵,只要敌人与烽火台之间未被山体遮挡,哨兵就会立即察觉。当然,按照这一军规,对于南侧的敌情各烽火台并不负责任。一旦哨兵发现敌情,他就会立即以狼烟或烽火的形式,向其南方的烽火台传递警报,直到位于最南侧的总部。
以图2中的长城为例,负责守卫的四个烽火台用蓝白圆点示意,最南侧的总部用红色圆点示意。如果红色星形标示的地方出现敌情,将被哨兵们发现并沿红色折线将警报传递到总部。当然,就这个例子而言只需两个烽火台的协作,但其他位置的敌情可能需要更多。 然而反过来,即便这里的4个烽火台全部参与,依然有不能覆盖的(黄色)区域。
图 2
另外,为避免歧义,我们在这里约定,与某个烽火台的视线刚好相切的区域都认为可以被该烽火台所监视。以图3中的长城为例,若A、B、C、D点均共线,且在D点设置一处烽火台,则A、B、C以及线段BC上的任何一点都在该烽火台的监视范围之内。
图 3
好了,倘若你是秦始皇的太尉,为不致出现更多孟姜女式的悲剧,如何在保证长城安全的前提下,使消耗的民力(建造的烽火台)最少呢?
输入格式:
输入在第一行给出一个正整数N(3 <= N <=105),即刻画长城边缘的折线顶点(含起点和终点)数。随后N行,每行给出一个顶点的x和y坐标,其间以空格分隔。注意顶点从南到北依次给出,第一个顶点为总部所在位置。坐标为区间 [-109, 109) 内的整数,且没有重合点。
输出格式:
在一行中输出所需建造烽火台(不含总部)的最少数目。
输入样例:
10
67 32
48 -49
32 53
22 -44
19 22
11 40
10 -65
-1 -23
-3 31
-7 59
输出样例:
2
解题思路:
用一个堆栈维护司令部看到当前点所必须的烽火台编号。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define maxn 100005
int n;
typedef long long ll;
struct point{
ll x;
ll y;
} p[maxn];
int S[maxn];
int vis[maxn];
bool judge(point &p1,point &p2,point &p3){
return (p2.y-p3.y)*(p1.x-p3.x)>(p1.y-p3.y)*(p2.x-p3.x);
}
int main(int argc, const char * argv[]) {
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%lld%lld",&p[i].x,&p[i].y);
S[]=;
int ptr=;
int cnt=;
for(int i=;i<n;i++){
if(ptr>=){
while(ptr>&&!judge(p[S[ptr-]],p[S[ptr-]],p[i])) {
ptr--;
}
vis[S[ptr-]]=;
}
S[ptr++]=i;
}
for(int i=;i<n;i++) if(vis[i]) cnt++;
cout<<cnt<<endl;
return ;
}
最新文章
- 配置SQL server远程连接(局域网)
- 一次关于使用status作为变量引发的bug及思考
- jquery-uploadify 上传
- C语言-10-位域与共用体
- 淘宝(阿里百川)手机客户端开发日记第八篇 Handler的使用方法
- 更换ubuntu apt-get 源
- T-SQL游标
- RHEL 6.3使用CentOS yum源 (redhat yum安装失败)
- 项目管理Project
- Delphi TRect函数例子
- Java sax、dom、pull解析xml
- 从浏览器直接转跳到APP具体页面---(魔窗)MagicWindow使用教程
- 【Vue 2.x】计算属性
- 关于cisco日志的配置
- Hadoop生态圈-Knox网关的应用案例
- java 字符串中参数化符号${}的解析
- C# HttpWebRequest 模拟下载
- java基础篇---XML解析(一)
- python --help查询python相关命令
- opencv3寻找最小包围矩形在图像中的应用-滚动条
热门文章
- linux下Nginx安装Zend Optimizer组件步骤
- QT加载qss
- 【JZOJ4964】【GDKOI2017模拟1.21】Rhyme
- 【JZOJ4747】【NOIP2016提高A组模拟9.3】被粉碎的线段树
- vue @click.native
- Resource Management in View Controllers
- hdu1532&;&;poj1273 最大流
- 在oracle中操作数据——使用特点的格式插入日期 sql函数的使用——日期函数
- 25-1 request模块介绍
- Spring Data JPA 查询结果返回至自定义实体