首页 > ACM题库 > HDU-杭电 > HDU 3761-Jungle Outpost-分治-[解题报告]HOJ
2015
04-10

HDU 3761-Jungle Outpost-分治-[解题报告]HOJ

Jungle Outpost

问题描述 :

There is a military base lost deep in the jungle. It is surrounded by n watchtowers with ultrasonic generators. In this problem watchtowers are represented by points on a plane.
Watchtowers generate ultrasonic field and protect all objects that are strictly inside the towers’ convex hull. There is no tower strictly inside the convex hull and no three towers are on a straight line.
The enemy can blow up some towers. If this happens, the protected area is reduced to a convex hull of the remaining towers.
Ideal Path

The base commander wants to build headquarters inside the protected area. In order to increase its security, he wants to maximize the number of towers that the enemy needs to blow up to make the headquarters unprotected.

输入:

The input begins with an integer T. The next T blocks each represents a case. The first line of each case contains a single integer n (3 ≤ n ≤ 50 000) – the number of watchtowers. The next n lines contain the Cartesian coordinates of watchtowers, one pair of coordinates per line. Coordinates are integer and do not exceed 106 by absolute value. Towers are listed in the order of traversal of their convex hull in clockwise direction.

输出:

The input begins with an integer T. The next T blocks each represents a case. The first line of each case contains a single integer n (3 ≤ n ≤ 50 000) – the number of watchtowers. The next n lines contain the Cartesian coordinates of watchtowers, one pair of coordinates per line. Coordinates are integer and do not exceed 106 by absolute value. Towers are listed in the order of traversal of their convex hull in clockwise direction.

样例输入:

2
3
0 0
50 50
60 10
5
0 0
0 10
10 20
20 10
25 0

样例输出:

1
2

转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526      
by—cxlove

题目:给出一个凸多边形,顶点为一些防御塔,保护范围是凸多形内部,不包括边界,在多边形内部选择一点,使得对方至少需要摧毁的塔防数量最多。
http://acm.hdu.edu.cn/showproblem.php?pid=3761 

首先感谢晴天哥哥的悉心指导。

首先需要明白的是一个问题,对于摧毁一定数量的塔防,怎样的方案是使得剩下的保护范围最小。

结论是摧毁连续多个顶点,这样是最优的,可以尝试证明一下。

对于5个顶点的多边形,删除两个顶点,可以尝试连续两个顶点,以及间隔一个顶点。

由于原多边形是凸边形,所以还是比较容易得到连续顶点最优,同理可得其它情况。

题目要求的是使对方尽可能多的摧毁至少需要摧毁的塔防,联系复杂度等等问题

二分答案,然后判断是否存在一个区域,保证能受保护。

对于每一次二分,枚举删除连续的顶点,形成新的边界,通过半平面交判断是否存在可行区域。

注意:边界上的点是不受保护的,所以只需要判断多边形的核的面积即可。

           当剩余的点在2个以及以下是,是肯定可行的。避免处理麻烦。

再看一看题目的范围,5W个顶点,半平面交至少肯定是要用nlgn的算法,其实听了晴天哥哥的说明,才知道,这题

二分+半平面交的nlgnlgn的算法都要卡掉,顿时吓尿了,难道有o(n)的半平面交算法???

多亏晴天哥哥的指导,其实zzy的半平面交算法是将所有向量按极角排序之后,维护了一个双端队列,排序部分达到nlgn的复杂度,其实后面只需要o(n)。然后再看这题,原先给的凸多形是有序的,而之后我们的连线的极角也是循环有序的,线性扫描一遍,找到最小的极角,便可以依次得到有序的向量,O(n)的线性sort,晴天哥哥太神了。

具体细节就要看每个人的习惯了,我将原来的顺序调整为逆序,半平面交的算法是针对向量的左侧,而极角是顺时针有序。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define eps 1e-10
#define N 50005
#define zero(a) (fabs(a)<eps)
using namespace std;
struct Point {
    double x,y;
    Point(){}
    Point(double tx,double ty){x=tx;y=ty;}
}p[N],q[N];
int n,m;
struct Segment{
    Point s,e;
    double angle;
    void get_angle(){angle=atan2(e.y-s.y,e.x-s.x);}
}seg[N];
double xmul(Point p0,Point p1,Point p2){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double Get_Area(Point pt[],int n){
    double area=0;
    for(int i=1;i<n-1;i++)
        area+=xmul(pt[0],pt[i],pt[i+1]);
    return fabs(area)/2;
}
Point Get_Intersect(Segment s1,Segment s2){
    double u=xmul(s1.s,s1.e,s2.s),v=xmul(s1.e,s1.s,s2.e);
    Point t;
    t.x=(s2.s.x*v+s2.e.x*u)/(u+v);t.y=(s2.s.y*v+s2.e.y*u)/(u+v);
    return t;
}
void HalfPlaneIntersect(Segment seg[],int n){
    int idx;
    for(int i=0;i<n;i++)
        if(seg[i].angle+eps<seg[(i+1)%n].angle&&seg[i].angle+eps<seg[(i-1+n)%n].angle){
            idx=i;
            break;
        }
    Segment deq[N];
    deq[0]=seg[idx];deq[1]=seg[(idx+1)%n];
    int head=0,tail=1;
    idx=(idx+2)%n;
    for(int i=2;i<n;i++,idx=(idx+1)%n){
        while(head<tail&&xmul(seg[idx].s,seg[idx].e,Get_Intersect(deq[tail],deq[tail-1]))<-eps) tail--;
        while(head<tail&&xmul(seg[idx].s,seg[idx].e,Get_Intersect(deq[head],deq[head+1]))<-eps) head++;
        deq[++tail]=seg[idx];
    }
    while(head<tail&&xmul(deq[head].s,deq[head].e,Get_Intersect(deq[tail],deq[tail-1]))<-eps) tail--;
    while(head<tail&&xmul(deq[tail].s,deq[tail].e,Get_Intersect(deq[head],deq[head+1]))<-eps) head++;
    m=0;
    if(tail==head) return;
    for(int i=head;i<tail;i++){
        q[m++]=Get_Intersect(deq[i],deq[i+1]);
    }
    if(tail>head+1)
        q[m++]=Get_Intersect(deq[head],deq[tail]);
}
int slove(int mid){
    if(n-mid<=2) return 1;
    for(int i=0;i<n;i++){
        seg[i].s=p[i];
        seg[i].e=p[(i+mid+1)%n];
        seg[i].get_angle();
    }
    HalfPlaneIntersect(seg,n);
    return zero(Get_Area(q,m));
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        for(int i=1;i<=n/2;i++) swap(p[i],p[n-i]);
        int ans,low=0,high=n,mid;
        while(low<=high){
            mid=(low+high)/2;
            if(slove(mid)){ans=mid;high=mid-1;}
            else low=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}



版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/7915167


  1. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.