Pagini recente » Cod sursa (job #1587815) | Cod sursa (job #839701) | Cod sursa (job #2565731) | Cod sursa (job #1125591) | Cod sursa (job #3245854)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,l,d,i,poz,s[1200002];
struct pct
{
double x,y;
int d;
}v[1200002];
bool sortare(pct p,pct q)
{
if(p.x<q.x)
return true;
if(p.x>q.x)
return false;
if(p.y<q.y)
return true;
if(p.y>q.y)
return false;
}
double her(pct a,pct b,pct c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y;
}
int main()
{
f>>n;
for(i=1; i<=n; i++)
{
f>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,sortare);
for(i=2; i<n; i++)
{
if(her(v[1],v[n],v[i])<=0)
{
v[i].d=1;
}
else
{
v[i].d=2;
}
}
int nr=0;
s[++nr]=1;
for(i=2; i<=n; i++)
{
if(v[i].d==1 or i==n)
{
while(her(v[s[nr-1]],v[s[nr]],v[i])<0 and nr>1)
{
nr--;
}
s[++nr]=i;
}
}
s[nr]=n;
for(i=n-1; i>=1; i--)
{
if(v[i].d==2 or i==1)
{
while(her(v[s[nr-1]],v[s[nr]],v[i])<0 and nr>1)
{
nr--;
}
s[++nr]=i;
}
}
g<<nr-1<<endl;
for(i=2; i<=nr; i++)
{
g<<fixed<<setprecision(6)<<v[s[i]].x<<" "<<v[s[i]].y<<" "<<endl;
}
return 0;
}