Pagini recente » Cod sursa (job #2265248) | Clasamentul arhivei de probleme | Cod sursa (job #1320463) | Cod sursa (job #1433553) | Cod sursa (job #1334689)
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct infasuratoare
{
double x,y;
} v[120001],minp,rasp[120005];
bool det(infasuratoare a, infasuratoare b, infasuratoare c)
{
if((a.x*b.y +b.x*c.y+c.x*a.y)-(a.y*b.x+b.y*c.x+c.y*a.x) > 0)
return true;
else return false;
}
int main()
{
int n,poz,k=2,j,i;
float x,y;
minp.x=1000000001;
minp.y=1000000001;
f>>n;
for( int i=1; i<=n; i++)
{
f>>x>>y;
if(x<minp.x || (x==minp.x && minp.y>y))
{
minp.x=x;
minp.y=y;
poz=i;
}
v[i].x=x;
v[i].y=y;
}
v[poz].x=v[n].x;
v[poz].y=v[n].y;
n=n-1;
for(int i=1; i<n; i++)
for(j=i+1; j<=n; j++)
{
if(det(minp,v[i],v[j]))
swap(v[i],v[j]);
}
rasp[1]=minp;
rasp[2]=v[1];
for(i=2; i<=n; i++)
{
while(det(rasp[k-1],rasp[k],v[i]))
k--;
rasp[++k].x=v[i].x;
rasp[k].y=v[i].y;
}
g<<k<<endl;
for(i=k; i>=1; i--)
g<<fixed<<setprecision(6)<<rasp[i].x<<" "<<rasp[i].y<<endl;
return 0;
}