Pagini recente » Cod sursa (job #1227920) | Cod sursa (job #2873622) | Cod sursa (job #2451178) | Cod sursa (job #3137429) | Cod sursa (job #1912473)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef long double ld;
struct punct
{
ld x,y;
};
#define nmax 120005
punct v[nmax];
int t[nmax];
ld det(punct a,punct b,punct c)
{
return a.x*b.y+b.x*c.y+a.y*c.x-b.y*c.x-a.y*b.x-a.x*c.y;
}
bool cmp(punct a,punct b)
{
return (a.y-v[1].y)*(b.x-v[1].x)>(a.x-v[1].x)*(b.y-v[1].y);
}
int main()
{
int n,k,ind,i;
f>>n;
ind=1;
for(i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
if(v[i].x<v[ind].x)
ind=i;
else
if(v[i].x==v[ind].x)
if(v[i].y<v[ind].y)
ind=i;
}
swap(v[1],v[ind]);
sort(v+2,v+n+1,cmp);
v[0].x=0;
v[0].y=0;
t[0]=0;
t[1]=1;
k=1;
ind=2;
// v[n+1]=v[1];
while(ind<=n)
{
if(det(v[t[k-1]],v[t[k]],v[ind])>0)
{
while(k>=2 and det(v[t[k-1]],v[t[k]],v[ind])>0)
k-=1;
k+=1;
t[k]=ind;
}
else
{
k+=1;
t[k]=ind;
}
ind+=1;
}
g<<k<<'\n';
// g<<fixed<<setprecision(6)<<v[t[1]].x<<" "<<v[t[1]].y<<'\n';
for(i=k;i>=1;i--)
g<<fixed<<setprecision(6)<<v[t[i]].x<<" "<<v[t[i]].y<<'\n';
return 0;
}