Pagini recente » Cod sursa (job #990959) | Cod sursa (job #655217) | Cod sursa (job #781849) | Cod sursa (job #3193231) | Cod sursa (job #1411462)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef int var;
struct punct
{
double x,y;
};
punct a[12005],t[12005];
var minimy,minimx;
bool cmp(punct b,punct c)
{
if((b.x-minimx)*(c.y-minimy)>(c.x-minimx)*(b.y-minimy))
return 0;
else
return 1;
}
int determinant(punct q,punct w,punct e)
{
return (q.x*w.y+w.x*e.y+e.x*q.y-e.x*w.y-w.x*q.y-q.x*e.y);
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
var n;
f>>n;
minimx=1000000015;
var poz1;
for(var i=1;i<=n;i++)
{
f>>a[i].x;
f>>a[i].y;
if(minimx>a[i].x)
{
minimx=a[i].x;
minimy=a[i].y;
poz1=i;
}
else
{
if(minimx==a[i].x)
if(minimy>a[i].y)
{
minimy=a[i].y;
poz1=i;
}
}
}
punct aux;
aux=a[poz1];
a[poz1]=a[1];
a[1]=aux;
sort(a+2,a+n+1,cmp);
var poz=1;
minimx=1000000015;
/* for(var i=1;i<=n;i++)
{
if(minimx>a[i].x)
{
minimx=a[i].x;
minimy=a[i].y;
poz=i;
}
else
{
if(minimx==a[i].x)
if(minimy>a[i].y)
{
minimy=a[i].y;
poz=i;
}
}
}*/
t[0].x=0;
t[0].y=0;
t[1]=a[1];
g<<a[poz].x<<" "<<a[poz].y;
var k=1;
for(var i=2;i<=n;i++)
{
if(determinant(t[k-1],t[k],a[i])>0)
{
while(determinant(t[k-1],t[k],a[i])>0)
k--;
k++;
t[k]=a[i];
}
else
{
k+=1;
t[k]=a[i];
}
}
/* for(var i=1;i<poz;i++)
if(determinant(t[k-1],t[k],a[i])<0)
{
while(determinant(t[k-1],t[k],a[i])<0)
k--;
k++;
t[k]=a[i];
}
else
{
k+=1;
t[k]=a[i];
}*/
g<<k<<'\n';
for(var i=k;i>=1;i--)
g<<setprecision(6)<<fixed<<t[i].x<<" "<<t[i].y<<'\n';
f.close();
g.close();
return 0;
}