2015
04-10

# 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.

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

by—cxlove

http://acm.hdu.edu.cn/showproblem.php?pid=3761

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

#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];
idx=(idx+2)%n;
for(int i=2;i<n;i++,idx=(idx+1)%n){
deq[++tail]=seg[idx];
}
m=0;
q[m++]=Get_Intersect(deq[i],deq[i+1]);
}
}
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;
}