POJ3348 凸包面積計算

題目： 給坐标，算凸包面積，每個牛占50，問能放多少牛

做法：面積除以50……套模闆吧…

CODE:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <climits>
#include<vector>
#include<iomanip>
#include <numeric>
#include<cmath>
#define foreach(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
#define REP(i,n) for(int i=0;i<n;++i)
using namespace std;

const double EPS = 1e-8;
inline int sign(double a)
{
    return a < -EPS ? -1 : a > EPS;
}

struct Point
{
    double x, y;
    Point()
    {
    }
    Point(double _x, double _y) :
        x(_x), y(_y)
    {
    }
    Point operator+(const Point&p) const
    {
        return Point(x + p.x, y + p.y);
    }
    Point operator-(const Point&p) const
    {
        return Point(x - p.x, y - p.y);
    }
    Point operator*(double d) const
    {
        return Point(x * d, y * d);
    }
    Point operator/(double d) const
    {
        return Point(x / d, y / d);
    }
    bool operator<(const Point&p) const
    {
        int c = sign(x - p.x);
        if (c)
            return c == -1;
        return sign(y - p.y) == -1;
    }
    double dot(const Point&p) const
    {
        return x * p.x + y * p.y;
    }
    double det(const Point&p) const
    {
        return x * p.y - y * p.x;
    }
    double alpha() const
    {
        return atan2(y, x);
    }
    double distTo(const Point&p) const
    {
        double dx = x - p.x, dy = y - p.y;
        return hypot(dx, dy);
    }
    double alphaTo(const Point&p) const
    {
        double dx = x - p.x, dy = y - p.y;
        return atan2(dy, dx);
    }
    void read()
    {
        scanf("%lf%lf", &x, &y);
    }
    double abs()
    {
        return hypot(x, y);
    }
    double abs2()
    {
        return x * x + y * y;
    }
    void write()
    {
        cout << "(" << x << "," << y << ")" << endl;
    }
};

#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))

#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

Point isSS(Point p1, Point p2, Point q1, Point q2)       //可求p1,p2 直線與q1，q2的焦點。。不過不确定
{
    double a1 = cross(q1,q2,p1), a2 = -cross(q1,q2,p2);
    Point temp;
    temp.x=sign((p1.x*a2+p2.x*a1)/(a1+a2))==0?0:(p1.x*a2+p2.x*a1)/(a1+a2);
    temp.y=sign((p1.y*a2+p2.y*a1)/(a1+a2))==0?0:(p1.y*a2+p2.y*a1)/(a1+a2);
    return temp;
}


vector<Point> convexHull(vector<Point> ps)
{
    int n = ps.size();
    if (n <= 1)
        return ps;
    sort(ps.begin(), ps.end());
    vector<Point> qs;
    for (int i = 0; i < n; qs.push_back(ps[i++]))
    {
        while (qs.size() > 1 && crossOp(qs[qs.size()-2],qs.back(),ps[i]) <= 0)
            qs.pop_back();
    }
    for (int i = n - 2, t = qs.size(); i >= 0; qs.push_back(ps[i--]))
    {
        while (qs.size() > t && crossOp(qs[qs.size()-2],qs.back(),ps[i]) <= 0)
            qs.pop_back();
    }
    qs.pop_back();
    return qs;
}
double calcArea(const vector<Point>&ps) {
	int n = ps.size();
	double ret = 0;
	for (int i = 0; i < n; ++i) {
		ret += ps[i].det(ps[(i + 1) % n]);
	}
	return ret / 2;
}
int main()
{
    int n;
    cin>>n;
    vector<Point>ps;
    vector<Point>qs;
    Point temp;
    for(int i=1; i<=n; i++)
    {
        temp.read();
        ps.push_back(temp);
    }
    qs=convexHull(ps);
    int sum=calcArea(qs)/50;
    cout<<sum<<endl;
}