Pagini recente » Cod sursa (job #581909) | Cod sursa (job #2141918) | Cod sursa (job #169705) | Cod sursa (job #834621) | Cod sursa (job #2548014)
//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int Max=120005;
int n;
struct pct
{
double x,y;
}p[Max],s[Max];
double cross(pct q,pct r,pct t)
{
return (r.y-q.y)*(t.x-q.x)-(t.y-q.y)*(r.x-q.x);
}
bool sortare(pct a,pct b)
{
return (cross(p[1],a,b)<0);
}
int main()
{
in>>n;
for(int i=1;i<=n;i++)
in>>p[i].x>>p[i].y;
int poz=1;
for(int i=2;i<=n;i++)
if(p[i].x<p[poz].x || (p[i].x==p[poz].x && p[i].y<p[poz].y))
poz=i;
swap(p[1],p[poz]);
sort(p+1,p+n+1,sortare);
int nr=0;
s[++nr]=p[1];
s[++nr]=p[2];
for(int i=3;i<=n;i++)
{
while(nr>=2 && cross(s[nr-1],s[nr],p[i])>0)
nr--;
s[++nr]=p[i];
}
out<<nr<<"\n";
out<<fixed;
for(int i=1;i<=nr;i++)
out<<setprecision(6)<<s[i].x<<" "<<s[i].y<<"\n";
return 0;
}