- 浏览: 388600 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (229)
- java编程 (4)
- java实用程序 (2)
- 算法设计 (34)
- 数据库 (8)
- ACM模板 (12)
- 技术术语 (1)
- java_web (3)
- php (22)
- eclipse (3)
- linux (25)
- linux命令使用心得 (3)
- web服务器 (8)
- IT知识 (2)
- 前端技术 (17)
- 开源软件 (5)
- vim (3)
- linux多线程 (9)
- web开发经验 (3)
- lua (5)
- linux编程 (3)
- smarty (1)
- mysql (4)
- Hive (2)
- 数据挖掘 (9)
- python (2)
- 生活 (1)
- C++ (2)
- 计算机 (1)
- objective-c (11)
- css (2)
- 游戏 (1)
- Mac (1)
最新评论
-
lr544463316:
我的怎么不行呀.....
Mysql Access denied for user ''@'localhost' to database 的一种解决方法 -
babaoqi:
使用时需要注意group_concat函数返回值的最大长度=g ...
mysql中的group_concat函数 -
代码能力弱成渣:
可以帮我看下我的代码么?我自己写的sam,也有ac过题的,但是 ...
求两个字符串的最长公共连续子序列(SAM实现) -
atgoingguoat:
有1000个?不过还是收藏下。
jquery常用的插件1000收集(转载)
source: http://poj.org/problem?id=3968
title: Jungle Outpost
题目简意:给出一个凸多边形,求至少删除多少个点后,多边形内的任意一点都得不到庇护。
/* 可以肯定,被移除的 这些点在凸多边形上是连续的,于是可以二分至少需要移除的点数k,然后 用ps[i]->ps[(i+mid+1)%n](0<=i<n)构造n条线段,对这n条线段代表的 半平面求交, 最后判断求出来的凸多边形的面积是否为0即可。 */ #include <cstdio> #include <cmath> #include <algorithm> using namespace std; const int N=50005; const double eps=1e-8; int sign(double d){ return d<-eps ? -1 : (d > eps); } struct point{ double x, y; point(double _x=0, double _y=0):x(_x), y(_y){} void read(){ scanf("%lf%lf", &x, &y); } void set(double _x, double _y){ x=_x; y=_y; } }ps[N], hull[N], pque[N]; struct seg{ point st, ed; double ang; void calang(){ ang = atan2(ed.y-st.y, ed.x-st.x); } }sque[N+10], segs[N+10]; int n; inline double xmul(point st1, point ed1, point st2, point ed2){ return (ed1.x - st1.x) * (ed2.y - st2.y) - (ed1.y - st1.y) * (ed2.x - st2.x); } point intersectPoint(point st1, point ed1, point st2, point ed2){ //求相交直线的交点 double t = xmul(st2, st1, st2, ed2) / ((ed1.y-st1.y) * (ed2.x-st2.x) - (ed1.x-st1.x) * (ed2.y-st2.y)); return point(st1.x+(ed1.x-st1.x)*t, st1.y+(ed1.y-st1.y)*t); } bool cmpseg(seg a, seg b){ return a.ang < b.ang; } //半平面交,第i个 半平面为segs[i].st->segs[i].ed的右侧,结果放在ps中确保不要有极端的 数据 //比如 相邻的 线段 虽然极角不一样但却平行! void halfPlaneInter(seg* segs, int sn, point* ps, int& pn){ int i, l, r; //由于问题的特殊性,这些线段已经是 有序的 了,并且不会有有两条线段极角相同 if(sn <= 0){ pn = 0; return; } if(sn <= 2){ segs[sn] = segs[0]; for(l = r = 0; r < sn; r++){ sque[r] = segs[r]; pque[r] = intersectPoint(segs[r].st, segs[r].ed, segs[r+1].st, segs[r+1].ed); } }else{ l = r = 0; sque[r++] = segs[0]; sque[r++] = segs[1]; pque[0] = intersectPoint(sque[0].st, sque[0].ed, sque[1].st, sque[1].ed); for(i = 2; i < sn; i++){ while(r-l >= 2 && sign(xmul(segs[i].st, segs[i].ed, segs[i].st, pque[r-2])) <= 0) r--; sque[r++] = segs[i]; pque[r-2] = intersectPoint(sque[r-2].st, sque[r-2].ed, sque[r-1].st, sque[r-1].ed); } //删除多余的 半平面 while(r-l >= 2){ bool flag = false; if(sign(xmul(sque[r-1].st, sque[r-1].ed, sque[r-1].st, pque[l])) <= 0){ flag = true; l++; } if(sign(xmul(sque[l].st, sque[l].ed, sque[l].st, pque[r-2])) <= 0){ flag = true; r--; } if(!flag) break; } //这里需要注意,最后的结果可能是一个无限平面. pque[r-1] = intersectPoint(sque[l].st, sque[l].ed, sque[r-1].st, sque[r-1].ed); } for(pn = 0, i = l; i < r; i++){ ps[pn++] = pque[i]; } } bool input(){ if(scanf("%d", &n)==EOF) return false; int i; for(i=0; i<n; i++){ ps[n-i-1].read(); //保证输入的点是逆时针的 } return true; } double area(point* ps, int pn){ if(pn<=1) return 0; int i; double ans; for(ps[pn]=ps[0], ans=i=0; i<pn; i++){ ans += (ps[i].x*ps[i+1].y-ps[i].y*ps[i+1].x); } return ans*0.5; } bool check(int mid){ int hn, i; for(i=0; i<n; i++){ segs[i].st=ps[i]; segs[i].ed=ps[(i+mid+1)%n]; } halfPlaneInter(segs, n, hull, hn); double s=area(hull, hn); return sign(s)==0; } void solve(){ int l, r, mid; l=1; r=(n-1)>>1; while(l<=r){ mid=(l+r)>>1; if(check(mid)){ r=mid-1; }else{ l=mid+1; } } int ans=r+1; printf("%d\n", ans); } int main(){ while(input()) solve(); return 0; }
发表评论
-
升序数组中求一个key出现的次数
2013-01-09 23:08 1108算法思路: 在排好序的数组,相同的数字是排列在一起的,所以只需 ... -
判断单链表是否有环
2013-01-08 19:07 920算法思路: 指针p1和p2的起始值均为链表的表头,指针p1每次 ... -
hdu3684
2011-11-15 20:11 930/* 刚开始打了个记录上下左右四个点的,一直tle。 ... -
hdu3686
2011-11-14 20:43 1035/* 无向图边的双连通分量,在同一个连通分量里的边之间 ... -
uva2819
2011-11-13 02:20 900source: http://livearchive.onli ... -
manacher算法
2011-11-11 00:06 2434const int LEN=110005; const ... -
hdu4118
2011-11-09 21:53 1192枚举每条边最多被经过的次数即可 #include ... -
hdu4115
2011-11-09 16:27 1040source: http://acm.hdu.edu.cn/ ... -
uva(Transitive Closure)
2011-11-08 14:45 918source: http://livearchive.onli ... -
zoj3500
2011-11-07 17:41 956求两个球的体积交或者并 #include <cs ... -
zoj3545
2011-11-04 18:18 867/* AC自动机 相当暴力的 解法: mark[i ... -
zoj3190
2011-11-04 17:34 1317/* * AC自动机,先对资源串和病毒串构成的字符串 ... -
zoj3228
2011-11-04 16:12 949/* * AC自动机,每个节点 添加一个d表示节点代 ... -
poj3691(DNA Repair)
2011-11-04 13:18 1481/* AC自动机,增设虚拟节点,求长度为n的字符串中包 ... -
hdu2825
2011-11-04 11:53 992/* AC自动机,增设虚拟节点,求长度为n的字符 ... -
hdu4095
2011-11-03 13:19 1020/* 第一步,构建BST,用第一个数作为bst的 ... -
zoj3540
2011-11-02 21:33 926/* 其实就是把总共的 放置次数减去不能放置的那些就行 ... -
poj1741(树的分治,基于边的 分治)
2011-11-02 20:25 3358/* 树基于边的分治算法,计算树中距离小于等于k的点 ... -
hdu2939
2011-10-29 18:36 859source: http://acm.hdu.edu.cn/s ... -
hdu3982
2011-10-29 10:20 947//半平面交+多边形和圆的交的面积 #include ...
相关推荐
* 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...
【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...
【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...
标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...
根据给定的文件信息,我们可以总结出一份详细的IT知识训练计划,主要针对编程竞赛和算法学习,特别是聚焦于POJ(Problem Online Judge)平台上的题目训练。这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165...
- **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...
* 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...
【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...
标题和描述中的“poj各种分类”主要指向的是在POJ(Peking University Online Judge)平台上,根据解题策略和算法类型对题目进行的分类。POJ作为一个知名的在线编程平台,提供了大量的算法练习题,适合从初学者到...
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
【标题】"POJ1201-Intervals" 是北京大学在线编程平台POJ上的一道题目,这道题目主要涉及计算机科学中的算法设计与分析,尤其是数据结构和时间复杂度优化方面的知识。 【描述】"北大POJ1201-Intervals 解题报告+AC...
【标题】"POJ1010-STAMPS"是一个编程题目,来源于北京大学的在线判题系统POJ(Problem Set of Peking University),这是一处训练程序员算法技能和编程能力的平台。该题目旨在考察参赛者对动态规划或贪心算法的理解...
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
标签"poj poj_27 poj27 poj2775"进一步确认了这是一道关于POJ平台的编程挑战,其中"poj_27"可能是表示第27类问题或者某种分类,而"poj27"可能是对"poj2775"的简写。 压缩文件中的"www.pudn.com.txt"可能是一个链接...
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告