Pagini recente » Cod sursa (job #556808) | Cod sursa (job #1841445) | Cod sursa (job #2367253) | Cod sursa (job #2483829) | Cod sursa (job #3124085)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct Point
{
double x,y;
};
Point a[120005];
long double Dist(Point A,Point B)
{
return abs(A.x-B.x)+abs(A.y-B.y);
}
int type(Point A,Point B)
{
if(A.x>B.x)
swap(A,B);
if(A.y>B.y)
return -1;
return 1;
}
bool f(Point A,Point B,Point C)
{
if(type(A,B)==-1)
{
if(A.y<=B.y)
{
if(C.x<B.x)
return 1;
return (Dist(C,{B.x,A.y})<Dist(C,{A.x,B.y}));
}
if(C.x>B.x)
return 1;
return (Dist(C,{B.x,A.y})<Dist(C,{A.x,B.y}));
}
if(A.y<=B.y)
{
if(C.x<A.x)
return 1;
return (Dist(C,{B.x,A.y})>Dist(C,{A.x,B.y}));
}
if(C.x>A.x)
return 1;
return (Dist(C,{B.x,A.y})>Dist(C,{A.x,B.y}));
}
int ord[120005];
bool cmp(int i,int j)
{
if(a[i].y!=a[j].y)
return (a[i].y<a[j].y);
return (a[i].x>a[j].x);
}
int sz;
int stk[120005];
int viz[120005];
int k;
Point ans[120005];
int main()
{
fin>>n;
for(int i=1; i<=n; i++)
fin>>a[i].x>>a[i].y;
fout<<fixed<<setprecision(12);
for(int i=1; i<=n; i++)
ord[i]=i;
sort(ord+1,ord+n+1,cmp);
stk[++sz]=ord[1];
viz[ord[1]]=1;
stk[++sz]=ord[2];
viz[ord[2]]=1;
for(int i=3; i<=n; i++)
{
int j=ord[i];
while(sz>=2 && f(a[stk[sz-1]],a[j],a[stk[sz]])==1)
{
viz[stk[sz]]=0;
sz--;
}
stk[++sz]=j;
viz[j]=1;
}
for(int i=1; i<=sz; i++)
ans[++k]=a[stk[i]];
sz=0;
stk[++sz]=ord[n];
stk[++sz]=ord[n-1];
for(int i=n-2; i>=1; i--)
{
int j=ord[i];
if(viz[j]==0)
{
while(sz>=2 && f(a[stk[sz-1]],a[j],a[stk[sz]])==1)
{
viz[stk[sz]]=0;
sz--;
}
stk[++sz]=j;
viz[j]=1;
}
}
for(int i=2; i<=sz; i++)
ans[++k]=a[stk[i]];
fout<<k<<"\n";
for(int i=1; i<=k; i++)
fout<<ans[i].x<<" "<<ans[i].y<<"\n";
return 0;
}