Pagini recente » Cod sursa (job #1868016) | Cod sursa (job #2127959) | Cod sursa (job #682681) | Cod sursa (job #1200997) | Cod sursa (job #1920511)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define ebs 1.0/1e12
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct {
double x;
double y;
}v[120002];
int infas[120002];
int lg,n;
bool cmp (punct a, punct b){
if (fabs(a.x-b.x) <= ebs)
return a.y < b.y;
return a.x < b.x;
}
double det (punct a, punct b, punct c){
return a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
}
void infasurare(){
for (int i = 1; i <= n; ++i){
while (lg > 1 && det(v[infas[lg-1]],v[infas[lg]],v[i]) <= 0)
lg--;
infas[++lg] = i;
}
int aux = lg;
for (int i = n; i >= 1; --i){
while (lg > aux && det(v[infas[lg-1]],v[infas[lg]],v[i]) <= 0)
lg--;
infas[++lg] = i;
}
}
int main (){
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> v[i].x >> v[i].y;
sort (v+1,v+n+1,cmp);
infasurare();
fout << lg-1 << "\n";
for (int i = 1; i < lg; ++i)
fout << fixed << setprecision(6) << v[infas[i]].x << " " << v[infas[i]].y << "\n";
}