Pagini recente » Cod sursa (job #2660885) | Cod sursa (job #2818234) | Cod sursa (job #289291) | Cod sursa (job #198782) | Cod sursa (job #616227)
Cod sursa(job #616227)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int N=120001;
struct punct{
double x,y;
}x[N],y[N],z[N];
bool comp(punct a,punct b){
return a.x<b.x;
}
int n,nr1,nr2;
int main(){
int i;
in>>n;
for(i=1;i<=n;i++){
in>>x[i].x>>x[i].y;
}
sort(&x[1],&x[n+1],comp);
y[++nr1]=x[1];
for(i=2;i<=n;i++){
while(nr1>1 && (x[i].y - y[nr1].y) * (x[i].x - y[nr1-1].x) <= (x[i].x - y[nr1].x) * (x[i].y - y[nr1-1].y))
--nr1;
y[++nr1]=x[i];
}
z[++nr2]=x[1];
for(i=2;i<=n;++i){
while(nr2>1 && (x[i].y - z[nr2].y) * (x[i].x - z[nr2-1].x) >= (x[i].x - z[nr2].x) * (x[i].y - z[nr2-1].y))
--nr2;
z[++nr2]=x[i];
}
out<<nr1+nr2-2<<"\n";
for(i=1;i<=nr1;++i)
out<<y[i].x<<" "<<y[i].y<<"\n";
for(i=nr2-1;i>1;--i)
out<<z[i].x<<" "<<z[i].y<<"\n";
return 0;
}