UVa 10432

Finding the area of a polygon in a circle is fairly trivial if you remember basic trigonometry or you can make use of Wikipedia (like I did). The solution here uses the fact that a polygon is made up of many triangles and the area for a triangle whose SideAngleSide are known can be obtained using area = 1/2 * side * side * sin(angle). Initially I had gone for Law of Cosines and the Heron's formula but I could not get an AC so here is the code...

#include<iostream>
#include <vector>
#include <cmath>
#include <cstdio>
using namespace std;
int main()
{
  double r,n;
 while(scanf("%lf%lf",&r,&n)!=EOF) {
   double res = n*.5*r*r*sin((2*M_PI/n));

  printf("%.3lf\n",res);
 }
  return 0;

}

Graham Scan

This is a standard computational geometry algorithm. It is used to find the convex hull of a set of points on a plane in O(n*log(n)). For more info check this out http://en.wikipedia.org/wiki/Graham_scan . The following is an implementation of the same :

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

class Point
{
    public:
        // (x, y)
        double first,second;
        Point():first(.0),second(.0){}
        Point(double _x,double _y):first(_x),second(_y){}
        friend ostream& operator << (ostream& os, const Point & ref);
};

// printer for Point
ostream& operator << (ostream& os, const Point & ref) {
    return os<<"("<<ref.first<<", "<<ref.second<<")"<<endl;
}


// lowest and the eft-most point
Point p1;

// comparator for the points -- sorts according to polar angles wrt to p1
class comparatorOfPoints
{
    public:
        bool operator () (const Point& p2, const Point& p3) const
        {
            // assuming three points p1,p2,p3
            // vector v1 = p2 - p1 and v2 = p3 - p1
            // vector cross product of v1*v2 > 0 iff p3 lies on left of v1
            return (p2.first - p1.first)*(p3.second - p1.second) - (p2.second - p1.second)*(p3.first - p1.first) >= 0;
        }
};

// USAGE
// 1) feed all points --> GrahamScan(deque<Point> _listOfPoints)
// 2) sort all the points --> deque<Point> buildSortedListOfPoints();
// 3) build convex hull --> deque<Point> buildConvexHull();
class GrahamScan
{
    private :

        // holds all the points in the plane
        deque<Point > listOfPoints;
    public:

        GrahamScan(deque<Point> _listOfPoints):listOfPoints(_listOfPoints){}
        GrahamScan(const GrahamScan & ref):listOfPoints(ref.listOfPoints){}

        // sorts the points using the comparator
        deque<Point> buildSortedListOfPoints();

        // finds the convex hull
        deque<Point> buildConvexHull();
};

deque<Point> GrahamScan::buildSortedListOfPoints() {
    // Sanity check
    if(listOfPoints.size()<3) return listOfPoints;

    // finds p1
    p1 = listOfPoints[0];
    int positionOfP1 = 0;
    for(int i = 1; i < listOfPoints.size(); ++i) {
        if(listOfPoints[i].second < p1.second) {
            p1 = listOfPoints[i];
            positionOfP1 = i;
        }
        else if(listOfPoints[i].second == p1.second) {
            if(listOfPoints[i].first < p1.first) {
                p1 = listOfPoints[i];
                positionOfP1 = i;
            }

        }
    }

    // leave p1 and sort the rest
    swap(listOfPoints[0], listOfPoints[positionOfP1]);

    sort(listOfPoints.begin()+1, listOfPoints.end(), comparatorOfPoints());

    return listOfPoints;
}


// utility function to print the stack
void printStack(stack<Point> sp) {
    cout<<"__STACK__"<<endl;
    while(!sp.empty()) {
        Point temp = sp.top();
        sp.pop();
        cout<<temp<<endl;

    }
    cout<<"-----------"<<endl;
}


deque<Point> GrahamScan::buildConvexHull() {
    // Sanity Check
    if(listOfPoints.size()<=3) return listOfPoints;

    stack<Point> stackOfPoints;
    stackOfPoints.push(listOfPoints[0]);
    stackOfPoints.push(listOfPoints[1]);

    for(int index = 2 ; index<listOfPoints.size(); ++ index) {
        // printStack(stackOfPoints);
        Point p2 = stackOfPoints.top();
        stackOfPoints.pop();
        Point p1 = stackOfPoints.top();
        stackOfPoints.pop();
        Point p3 = listOfPoints[index];
        int turn = (p2.first - p1.first)*(p3.second - p1.second) - (p2.second - p1.second)*(p3.first - p1.first);
        if(turn == 0) {
            // ignore intermediate collinear points
            stackOfPoints.push(p1);
            stackOfPoints.push(p3);
            continue;
        }
        else if(turn > 0) {
            stackOfPoints.push(p1);
            stackOfPoints.push(p2);
            stackOfPoints.push(p3);
            continue;
        }
        else if(turn < 0) {
            // cout<<"encountered a right turn for " <<p3;
            stackOfPoints.push(p1);
            Point p2,p1;
            int _turn = turn;
            while(stackOfPoints.size() >= 2 && _turn <= 0) {
                printStack(stackOfPoints);
                p2 = stackOfPoints.top();
                stackOfPoints.pop();
                p1 = stackOfPoints.top();
                stackOfPoints.pop();
                _turn = (p2.first - p1.first)*(p3.second - p1.second) - (p2.second - p1.second)*(p3.first - p1.first);
                cout<<"turn = "<<_turn<<endl;
            }
            if(_turn > 0) {
                cout<<"right turn resolved for " <<p3;
                stackOfPoints.push(p1);
                stackOfPoints.push(p2);
                stackOfPoints.push(p3);
                printStack(stackOfPoints);
                continue;
            }

            // Sanity check
            else if(stackOfPoints.size()<2) {
                cout<<"can not from a convex hull due to stack underflow"<<endl;
                return deque<Point>();
            }
        }
    }
    deque<Point> convexHull;
    while(!stackOfPoints.empty()) {
        convexHull.push_front(stackOfPoints.top());
        stackOfPoints.pop();
    }
    return convexHull;
}


// driver
int main() {
    deque<Point> pointsOnPlane;
    pointsOnPlane.push_back(Point(5,5));
    pointsOnPlane.push_back(Point(1,-1));
    pointsOnPlane.push_back(Point(0,0));
    pointsOnPlane.push_back(Point(2,2));
    pointsOnPlane.push_back(Point(-1,-1));
    pointsOnPlane.push_back(Point(-5,4));
    GrahamScan grahamScan(pointsOnPlane);
    grahamScan.buildSortedListOfPoints();
    deque<Point> convexHull=grahamScan.buildConvexHull();
    for(int i=0;i<convexHull.size();i++) {
        cout<<convexHull[i];
    }

    return 0;
}