Pagini recente » Cod sursa (job #2183054) | Cod sursa (job #1529938) | Cod sursa (job #332607) | Cod sursa (job #2793869) | Cod sursa (job #2922784)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point
{
double x;
double y;
};
int n;
Point a[120005];
bool viz[120005];
bool cmp(Point A,Point B)
{
if(A.y==B.y)
return A.x<B.x;
return A.y<B.y;
}
long long f(Point A,Point B,Point C)
{
int a,b,c;
a=B.y-A.y;
b=A.x-B.x;
c=1LL*A.y*(B.x-A.x)-1LL*A.x*(B.y-A.y);
return 1LL*a*C.x+1LL*b*C.y+c;
}
int s[120005],k;
int main()
{
fin>>n;
for(int i=1; i<=n; i++)
fin>>a[i].x>>a[i].y;
/// cout<<f({1,0},{0,1},{0,0});
sort(a+1,a+n+1,cmp);
s[++k]=1;
s[++k]=2;
viz[2]=1;
for(int i=3; i<=n; i++)
{
while(k>=2 && f(a[s[k-1]],a[s[k]],a[i])>=0)
{
viz[s[k]]=0;
k--;
}
viz[i]=1;
s[++k]=i;
}
for(int i=n; i>=1; i--)
{
if(viz[i]==0)
{
while(k>=2 && f(a[s[k-1]],a[s[k]],a[i])>=0)
k--;
s[++k]=i;
}
}
fout<<k-1<<"\n";
for(int i=1; i<k; i++)
fout<<setprecision(12)<<fixed<<a[s[i]].x<<" "<<a[s[i]].y<<"\n";
return 0;
}