Pagini recente » Cod sursa (job #436864) | Istoria paginii utilizator/fiichs | Cod sursa (job #1589461) | Cod sursa (job #833675) | Cod sursa (job #2262619)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DIM 120010
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int n,i,k,d[DIM];
double nr1,nr2;
struct punct {
double x;
double y;
};
punct v[DIM];
int cmp2 (punct a, punct b){
if (a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
int cadran (punct a){
if (a.x >= 0 && a.y >= 0)
return 1;
return 2;
}
int cmp (punct a, punct b){
if (cadran(a) != cadran (b))
return cadran (a) < cadran (b);
if (a.x*b.y - b.x*a.y != 0)
return a.x*b.y - b.x*a.y > 0;
return (a.x*a.x + a.y*a.y) < (b.x*b.x + b.y*b.y);
}
int verif (punct a, punct b, punct c){
if ( (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x) <=0 )
return 1;
return 0;
}
int main (){
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort (v+1,v+n+1,cmp2);
/// normalizare
nr1 = v[1].x, nr2 = v[1].y;
for (i=1;i<=n;i++)
v[i].x -= nr1, v[i].y -= nr2;
/// sortare unghi
sort (v+1,v+n+1,cmp);
d[1] = 1;
d[2] = 2;
k = 2;
for (i=3;i<=n;i++){
while (k >= 2 && verif (v[d[k-1]],v[d[k]],v[i]))
k--;
d[++k] = i;
}
fout<<k<<"\n";
for (i=1;i<=k;i++)
fout<<setprecision(6)<<fixed<<v[d[i]].x + nr1<<" "<<v[d[i]].y + nr2<<"\n";
return 0;
}