Cod sursa(job #830183)

Utilizator RolaindGhiuta Andrei Rolaind Data 6 decembrie 2012 15:04:56
Problema Rubarba Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<fstream>
#include <algorithm>

#define max 120003
int c,p,u,t,w;
using namespace std;
ifstream f("rubarba.in");
ofstream g("rubarba.out");
struct Punct{int x,y;};
Punct a[max],stack[max];
int n,i,k;
bool cmp(Punct a, Punct b)
{
if(a.x < b.x || (a.x == b.x && a.y < b.y)) return true;
return false;
}
int semn(Punct a , Punct b, Punct c)
{
if((b.x * c.y + a.x * b.y + c.x * a.y- a.y * b.x - c.x * b.y - a.x * c.y) >=0) return 1;
else  return 0;
}

int main()
{
c=0;p=0;t=0;w=0;
f>>n;
for(i = 1; i <= n; i++)     f>>a[i].x>>a[i].y;
sort(a + 1, a + n + 1, cmp);
stack[1]=a[1];
k = 1;
for(i = 2; i <= n; i++)
{
while(k > 1 && !semn(stack[k-1], stack[k], a[i])) k--;
stack[++k]=a[i];
}
for(i = n - 1; i >= 1; i--)
{
while(!semn(stack[k-1], stack[k], a[i]))k--;
stack[++k]=a[i];
}

g<<k-1<<'\n';
p=stack[1].x;
w=stack[1].y;
for(i = 1; i <= k-1 ; i++) { g<<stack[i].x<<' '<<stack[i].y<<'\n';
if(stack[i].x>c)
c=stack[i].x;
if(stack[i].x<p)
p=stack[i].x;
if(stack[i].y>t)
t=stack[i].y;
if(stack[i].y<w)
w=stack[i].y;

}
u=(c-p)*(t-w);
g<<u;
g.close();

return 0;

}