Pagini recente » Cod sursa (job #2832658) | Cod sursa (job #1146512) | Cod sursa (job #41934) | Borderou de evaluare (job #2016072) | Cod sursa (job #3177901)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int Nmax = 120005;
const long double eps = 1e-12;
int st[Nmax];
bool used[Nmax];
struct punct{
long double x;
long double y;
} p[Nmax];
bool cmp(punct a, punct b){
if(a.y == b.y)
return (a.x<b.x);
return(a.y<b.y);
}
bool check(punct a, punct b, punct c){
long double r = (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
if(r<=eps)
return 1;
return 0;
}
int main()
{
int n,i,k,sgn;
fin >> n;
for(i=1;i<=n;i++)
fin >> p[i].x >> p[i].y;
sort(p+1,p+n+1,cmp);
k = 0;
st[++k] = 1; st[++k] = 2; sgn = 1; used[1] = used[2] = 1;
for(i=3;i>0;i+=sgn){
if(!used[i]){
while(k>1 && check(p[st[k-1]],p[st[k]],p[i])){
used[st[k]] = 0;
k--;
}
st[++k] = i; used[i] = 1;
}
if(i == n)
sgn = -1;
}
fout << k << '\n';
fout << setprecision(6) << fixed;
for(i=1;i<=k;i++)
fout << p[st[i]].x << " " << p[st[i]].y << '\n';
return 0;
}