Pagini recente » Cod sursa (job #165034) | Cod sursa (job #200790) | Cod sursa (job #3253876) | Cod sursa (job #2145966) | Cod sursa (job #2284269)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int i,n,k;
struct ceva
{
double x,y;
}v[120002],s[120002];
int det(double xa,double ya,double xb,double yb,double xc,double yc)
{
if((xb-xa)*(yc-ya)-(xc-xa)*(yb-ya)>=0)return 1;
else return 0;
}
int cmp(ceva a,ceva b)
{
if(a.x<b.x || (a.x==b.x && a.y<b.y))return true;
return false;
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,cmp);
s[1]=v[1];
k=1;
for(i=2;i<=n;i++)
{
while(k>1 && det(s[k-1].x,s[k-1].y,s[k].x,s[k].y,v[i].x,v[i].y))
{
k--;
}
k++;
s[k]=v[i];
}
for(i=n-1;i>=1;i--)
{
while(!det(s[k-1].x,s[k-1].y,s[k].x,s[k].y,v[i].x,v[i].y))
{
k--;
}
k++;
s[k]=v[i];
}
g<<setprecision(6)<<fixed;
g<<k-1<<'\n';
for(i=1;i<=k-1;i++)
{
g<<s[i].x<<" "<<s[i].y<<'\n';
}
return 0;
}