10065

Can read about orientation here

Idea comes from the slope comparison.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

struct point{
	double x,y;
};
vector<point>pp;
double area(int n,vector<point> arr)
{
	double ans = 0.0;
	for(int i=0;i<n;i++)
	{
		ans += (arr[i].x*arr[(i+1)%n].y - arr[i].y*arr[(i+1)%n].x);
	}
	return fabs(ans/2.0);
}
int checkCross(point p, point q, point r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;  // colinear
    return (val > 0)? 1: 2; // clock or counterclock wise
}

int convexCalc(int n,vector<point> arr)
{
	point tmp;
	pp.clear();
	int leftMost=0;
	for(int i=1;i<n;i++)
	{
		if(arr[i].x<arr[leftMost].x)
		leftMost=i;
	}
	int left=leftMost,j;
	do
	{
		pp.push_back(arr[left]);
		j = (left+1)%n;
		for(int i=0;i<n;i++)
		{
			if( checkCross(arr[left],arr[i],arr[j])==2 )
			j=i;
		}
		left=j;
	}while(leftMost!=left);
	return pp.size();
}

bool cmp(point a,point b)
{
	if(a.x!=b.x)
	return a.x<b.x;
	return a.y<b.y;
}
int main()
{
	int n,kase=1;
	vector<point>arr;
	point tmp;
	double ans,ans2;
	while(scanf("%d",&n),n)
	{
		arr.clear();
		for(int i=0;i<n;i++)
		{
			scanf("%lf%lf",&tmp.x,&tmp.y);
			arr.push_back(tmp);
		}
		ans = area(n,arr);
		int cnt = convexCalc(n,arr);
		ans2 = area(cnt,pp);
		printf("Tile #%d\n",kase++);
		ans = ((ans2-ans)/ans2)*100;
		printf("Wasted Space = %.2lf %%\n\n",ans);
	}
	return 0;
}