Pagini recente » Cod sursa (job #1091271) | Cod sursa (job #1355339) | Cod sursa (job #692158) | Cod sursa (job #2319950) | Cod sursa (job #2231289)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n,solve[150000];
struct poz{
double x;
double y;
};
poz v[150000];
bool comp(poz a, poz b)
{
if(a.x<b.x)
return true;
else if(a.x==b.x && a.y<b.y)
return true;
return false;
}
bool ok(int a, int b, int c)
{
double delta,a1=v[a].x,a2=v[b].x,a3=v[c].x,b1=v[a].y,b2=v[b].y,b3=v[c].y;
delta=a1*b2+a2*b3+a3*b1-a3*b2-a1*b3-a2*b1;
if(delta<0)
return false;
else
return true;
}
int main()
{
in >> n;
for(int i=1; i<=n; i++)
{
in >> v[i].x >> v[i].y;
}
sort(v+1,v+1+n,comp);
solve[1]=1;
solve[2]=2;
int k=2;
for(int i=3; i<=n; i++)
{
if(ok(solve[k],solve[k-1],i))
{
solve[++k]=i;
}
else
{
while(!ok(solve[k],solve[k-1],i) && k>=2)
{
k--;
}
solve[++k]=i;
}
}
solve[++k]=n-1;
for(int i=n-2; i>=1; i--)
{
if(ok(solve[k],solve[k-1],i))
{
solve[++k]=i;
}
else
{
while(!ok(solve[k],solve[k-1],i) && k>=2)
{
k--;
}
solve[++k]=i;
}
}
out << k-1 << '\n';
for(int i=k-1; i>=1; i--)
{
out << fixed << setprecision(6) << v[solve[i]].x << ' ' << fixed << setprecision(6) << v[solve[i]].y << '\n';
}
return 0;
}