`

poj3968

 
阅读更多

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;
}
 
0
1
分享到:
评论

相关推荐

    POJ算法题目分类

    * 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...

    POJ.rar_poj java_poj1048

    【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...

    POJ_3131.zip_POJ 八数码_poj

    标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...

    POJ1159-Palindrome

    【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...

    POJ2002-Squares

    【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...

    jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c

    标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...

    poj训练计划.doc

    根据给定的文件信息,我们可以总结出一份详细的IT知识训练计划,主要针对编程竞赛和算法学习,特别是聚焦于POJ(Problem Online Judge)平台上的题目训练。这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...

    poj题目分类

    * 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...

    POJ1837-Balance

    【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...

    poj各种分类

    标题和描述中的“poj各种分类”主要指向的是在POJ(Peking University Online Judge)平台上,根据解题策略和算法类型对题目进行的分类。POJ作为一个知名的在线编程平台,提供了大量的算法练习题,适合从初学者到...

    poj 3414解题报告

    poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告

    POJ1201-Intervals

    【标题】"POJ1201-Intervals" 是北京大学在线编程平台POJ上的一道题目,这道题目主要涉及计算机科学中的算法设计与分析,尤其是数据结构和时间复杂度优化方面的知识。 【描述】"北大POJ1201-Intervals 解题报告+AC...

    POJ1010-STAMPS

    【标题】"POJ1010-STAMPS"是一个编程题目,来源于北京大学的在线判题系统POJ(Problem Set of Peking University),这是一处训练程序员算法技能和编程能力的平台。该题目旨在考察参赛者对动态规划或贪心算法的理解...

    poj 1012解题报告

    poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告

    poj 2329解题报告

    poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告

    POJ1503解答,正确答案(已通过POJ)

    POJ1503解答 POJ1503解答,正确答案(已通过POJ)

    poj2775.rar_poj_poj 27_poj27_poj2775

    标签"poj poj_27 poj27 poj2775"进一步确认了这是一道关于POJ平台的编程挑战,其中"poj_27"可能是表示第27类问题或者某种分类,而"poj27"可能是对"poj2775"的简写。 压缩文件中的"www.pudn.com.txt"可能是一个链接...

    poj 1659解题报告

    poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告

Global site tag (gtag.js) - Google Analytics