题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3761
Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

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.

Input

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.

Output

For each case, write to the output the number of watchtowers the enemy has to blow up to compromise headquarters protection if the headquarters are placed optimally.

Sample Input

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

Sample Output

1
2

Problem solving report:

Description: 求出最大需要炸毁的塔楼数量，以使总部不受保护。
Problem solving: 二分答案，判半平面交是否存在，连续销毁几个点比分开销毁的做法更优。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50010;
const double eps = 1e-8;
int n;
typedef struct point {
    double x, y;
}vect;
vect p[MAXN];
struct line {
    vect p;
    point u, v;
};
int pnz(double x) {
    return x > eps ? 1 : x < -eps ? -1 : 0;
}
vect operator - (const point& a, const point& b) {
    return (vect){a.x - b.x, a.y - b.y};
}
double Cross(const vect& a, const vect& b) {
    return a.x * b.y - b.x * a.y;
}
bool Onleft(const point& p, const line& l) {
    return pnz(Cross(l.p, p - l.u)) > 0;
}
point Inter(const line& a, const line& b) {
    double t = Cross(b.p, a.u - b.u) / Cross(a.p, b.p);
    return (point){a.u.x + t * a.p.x, a.u.y + t * a.p.y};
}
bool Check(int s) {
    line Sline[n];
    for (int i = 0; i < n; i++) {
        int j = (i + s + 1) % n;
        Sline[i] = (line){p[j] - p[i], p[i], p[j]};
    }
    int Q[n] = {0};
    point Spt[n];
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        while (l < r && !Onleft(Spt[r - 1], Sline[i]))
            r--;
        while (l < r && !Onleft(Spt[l], Sline[i]))
            l++;
        Q[++r] = i;
        if (!(pnz(Cross(Sline[i].p, Sline[Q[r - 1]].p)))) {
            r--;
            if (Onleft(Sline[i].u, Sline[Q[r]]))
                Q[r] = i;
        }
        else Spt[r - 1] = Inter(Sline[Q[r]], Sline[Q[r - 1]]);
    }
    while (l < r && !Onleft(Spt[r - 1], Sline[Q[l]]))
        r--;
    while (l < r && !Onleft(Spt[l], Sline[Q[r]]))
        l++;
    return r - l > 1;
}
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);
        reverse(p, p + n);
        int l = 1, r = n - 2, mid;
        while (l < r) {
            mid = ((r - l) >> 1) + l;
            if (Check(mid))
                l = mid + 1;
            else r = mid;
        }
        printf("%d\n", l);
    }
    return 0;
}