Pagini recente » Cod sursa (job #1111084) | Cod sursa (job #1331296) | Cod sursa (job #131815) | Cod sursa (job #3256680) | Cod sursa (job #2544558)
#include <bits/stdc++.h>
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
#define x first
#define y second
#define EPSILON 1
typedef std::pair<double, double> pd;
pd list[120005];
int stack[120005];
int head, n;
bool check[120005];
bool verif_conex(pd p1, pd p2, pd p3);
int main()
{
fin>>n;
for(int i=1; i<=n; ++i) fin>>list[i].x>>list[i].y;
std::sort(list+1, list+n+1);
stack[1]=1; stack[2]=2; check[2]=true; head=2;
for(int i=1, p=1; i; i+=(p=(i==n?-p:p))){
if(check[i]) continue;
while(head>=2 && !verif_conex(list[stack[head-1]], list[stack[head]], list[i])) check[stack[head--]]=false;
check[i]=true;
stack[++head]=i;
}
fout<<head-1<<"\n";
fout<<std::fixed<<std::setprecision(8);
while(--head) fout<<list[stack[head]].first<<" "<<list[stack[head]].second<<"\n";
return 0;
}
bool verif_conex(pd p1, pd p2, pd p3){
return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y)<EPSILON;
}