原 初学算法 - 求凸包的Garham's

Algorithm CONVEXHULL(P)
Input. A set P of points in the plane.
Output. A list containing the vertices of CH(P) in clockwise order.
 Sort the points by x-coordinate, resulting in a sequence p1,..., pn.
 Put the points p1 and p2 in a list Lupper, with p1 as the first point.
 for i ← 3 to n
     do Append pi to Lupper.
         while Lupper contains more than two points and the last three points in Lupper do not make a right turn
             do Delete the middle of the last three points from Lupper.
 Put the points pn and pn−1 in a list Llower 6 , with pn as the first point.
 for i ← n−2 downto 1
     do Append pi to Llower.
         while Llower contains more than 2 points and the last three points in Llower do not make a right turn
             do Delete the middle of the last three points from Llower.
 Remove the first and the last point from Llower to avoid duplication of the points where the upper and lower hull meet.
 Append Llower to Lupper, and call the resulting list L.
 return L

/**
 * Calculate the doubled directed area of pqs
 */
long long Area2( Point p, Point q, Point s)
{
    return p.x*q.y - p.y*q.x
          +q.x*s.y - q.y*s.x
          +s.x*p.y - p.x*s.y;
}

//Determinate whether s is on the left side of a directed line p->q
bool ToLeft( Point p, Point q, Point s)
{
    return Area2(p,q,s)>0;
}

/**
 Created on 2015-10-12 11:24:04

 Description : Generate the Convex Hull via the Graham's Scan Algorithm
               Time Cost : O(nlogn)
               Thanks to Tsinghua Univ. MOOC Computational Geometry 2015
               As the answer of CG2015 PA1-1 Convex Hull
               (http://dsa.cs.tsinghua.edu.cn/oj/course.shtml?courseid=39)

 Author: ChenZheng / Arc001
 Email : chenzheng17@yahoo.com
 Copyright 2015 Xi'an University of Posts & Telecommunications
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <list>

using namespace std;

enum Point_Status {isExtreme, notExtreme};

struct Point{
    long long x,y;
    int index;
    Point_Status status;

    bool operator < (const Point & rhs) const
    {
        if(x == rhs.x)
        {
            return y < rhs.y;
        }
        return x < rhs.x;
    }
};

long long Area2( Point p, Point q, Point s); //这里不再重复
bool ToLeft( Point p, Point q, Point s);

Point S[100005];
list<Point> upper_hull, lower_hull;

int main()
{
    int n;
    long long ans = 1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&S[i].x,&S[i].y);
        S[i].index = i;
        S[i].status = notExtreme;
    }

    sort(&S[1],&S[n+1]);

    upper_hull.push_back(S[1]);
    upper_hull.push_back(S[2]);

    list<Point>::iterator it,it2,it3;
    for(int i=3; i<=n; i++)
    {
        upper_hull.push_back(S[i]);
        it = it2 = it3 = upper_hull.end();
        --it; --it; --it;
        --it2; --it2;
        --it3;
        //cout<<it3->index<<" pushed!"<<endl;

        while(upper_hull.size()>2 && ToLeft(*it,*it2,*it3))
        {
            upper_hull.erase(it2);
            //cout<<it2->index<<" deleted! "<<it3->index<<" "<<Area2(*it,*it2,*it3)<<endl;
            it = it2 = it3 = upper_hull.end();
            --it; --it; --it;
            --it2; --it2;
            --it3;
        }
        //cout<<upper_hull.size()<<endl<<endl;
    }
    upper_hull.pop_back();

    lower_hull.push_back(S[n]);
    lower_hull.push_back(S[n-1]);

    for(int i=n-2; i>=1; i--)
    {
        lower_hull.push_back(S[i]);

        it = it2 = it3 = lower_hull.end();
        --it; --it; --it;
        --it2; --it2;
        --it3;
        while(lower_hull.size()>2 && ToLeft(*(it),*(it2),*(it3)))
        {
            lower_hull.erase(it2);
            it = it2 = it3 = lower_hull.end();
            --it; --it; --it;
            --it2; --it2;
            --it3;
        }
    }
    lower_hull.pop_back();

    //cout<<lower_hull.size()<<endl;
    int count_vertex = 0;
    for(it = upper_hull.begin(); it != upper_hull.end(); it++)
    {
        S[it->index].status = isExtreme;
        //cout<<it->index<<endl;
        count_vertex++;
    }

    for(it = lower_hull.begin(); it != lower_hull.end(); it++)
    {
        S[it->index].status = isExtreme;
        //cout<<it->index<<endl;
        count_vertex++;
    }

    for(int i=1; i<=n; i++){        //这里在计算这道题的答案，与算法关系不大
        if(S[i].status == isExtreme)
        {
            ans *= i;
            ans %= (n+1);
            //cout<<i<<endl;
        }
    }

    ans *= count_vertex;
    ans %= (n+1);

    printf("%lld\n",ans);
    return 0;
}