POJ 3348 Cows凸包

Cows
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 12101
 
Accepted: 5243
Description
Your friend to the south is interested in building fences and turning plowshares into swords. In order to help with his overseas adventure, they are forced to save money on buying fence posts by using trees as fence posts wherever possible. Given the locations of some trees, you are to help farmers try to create the largest pasture that is possible. Not all the trees will need to be used.
However, because you will oversee the construction of the pasture yourself, all the farmers want to know is how many cows they can put in the pasture. It is well known that a cow needs at least 50 square metres of pasture to survive.
Input
The first line of input contains a single integer, n (1 ≤ n ≤ 10000), containing the number of trees that grow on the available land. The next n lines contain the integer coordinates of each tree given as two integers x and y separated by one space (where -1000 ≤ x, y ≤ 1000). The integer coordinates correlate exactly to distance in metres (e.g., the distance between coordinate (10; 11) and (11; 11) is one metre).
Output
You are to output a single integer value, the number of cows that can survive on the largest field you can construct using the available trees.
Sample Input

4
0 0
0 101
75 0
75 101

Sample Output

151

Source
CCC 2007
 
参考資料:
https://blog.csdn.net/peng0614/article/details/81193484
凸包面積:
凸包の辺の点セットの上で、1つの基点を選択して、それから残りの辺はそれぞれ基点と三角形を構成して、面積を求めます.(ここで三角形の面積は平行四角形の面積を2で割って、平行四角形の面積は基点が辺の2点に向かうベクトルのフォークの型長で、ベクトルのフォークの式で計算することができて、最後に2で割る).
 

#include 
#include 
#include 
#include 
using namespace std;
struct Point
{
    int x;
    int y;
    Point(int xx=0,int yy=0)
    {
        x = xx;
        y = yy;
    }
};
typedef struct Point Point;

Point p[10005];
int n;

int cmp(Point a,Point b)
{
    if(a.x == b.x)
    {
        return a.y u;
vector d;

int getCross(Point a,Point b)
{
    return a.x*b.y - a.y*b.x;
}
bool isclock(Point p0,Point p1,Point p2)
{
    Point a(p1.x-p0.x,p1.y-p0.y);
    Point b(p2.x-p0.x,p2.y-p0.y);
    if(getCross(a,b)<0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

double getarea(Point p0,Point p1,Point p2)
{
    Point a(p1.x-p0.x,p1.y-p0.y);
    Point b(p2.x-p0.x,p2.y-p0.y);
    double tmp = getCross(a,b);
    if(tmp<0)
    {
        tmp = -tmp;
    }
    return tmp / 2.0;
}


int main()
{
    scanf("%d",&n);
    for(int i=0; i1 && isclock(u[s-2],u[s-1],p[i])==false;s--)
        {
            u.pop_back();
        }
        u.push_back(p[i]);
    }

    d.push_back(p[n-1]);
    d.push_back(p[n-2]);
    for(int i=n-3;i>=0;i--)
    {
        for(int s = d.size();s>1 && isclock(d[s-2],d[s-1],p[i])==false;s--)
        {
            d.pop_back();
        }
        d.push_back(p[i]);
    }

    for(int i=1;i