Pagini recente » Cod sursa (job #3147303) | Cod sursa (job #4030) | Cod sursa (job #1489993) | Cod sursa (job #2791676) | Cod sursa (job #717744)
Cod sursa(job #717744)
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in"); ofstream g("infasuratoare.out");
struct punct {double x, y, p;};
punct v[120005], stv[120005];
double x, y;
int i, j, n, b, mi;
inline bool comp (punct fx, punct fy){ return fx.p<fy.p; }
inline bool intoarcere (double x1, double y1, double x2, double y2, double x3, double y3){
double rz;
rz=x1*y2+x3*y1+x2*y3-x3*y2-x2*y1-x1*y3;
if (rz>0.0) return 1; else return 0;
}
int main(){
//citirea si cautarea celui mai din stanga-jos punct
y=1000000001.0; x=10000000001.0;
f>>n;
for (i=1; i<=n; i++){
f>>v[i].x>>v[i].y;
if (v[i].x<x || (v[i].x==x && v[i].y<y)){
mi=i; y=v[i].y; x=v[i].x;
}
}
//calculare unghiurilor polare
for (i=1; i<=n; i++) {
if (i!=mi) {
if (v[i].x==x) v[i].p=1000000001.0;
else if (v[i].y==y) v[i].p=0.0;
else v[i].p=(v[i].y-y)/(v[i].x-x);
}
}
//am grija ca punctul de plecare sa fie primul in stiva
v[mi].p=-2000000000.0;
//sortarea dupa unghiul polar
sort (v+1, v+n+1, comp);
//inserarea primelor doua elemente in stiva
stv[1].x=v[1].x; stv[1].y=v[1].y;
stv[2].x=v[2].x; stv[2].y=v[2].y;
b=2;
//rezolvarea stivei
for (i=3; i<=n; i++){
b++; stv[b].x=v[i].x; stv[b].y=v[i].y;
while (b>2 && intoarcere (stv[b-2].x, stv[b-2].y, stv[b-1].x, stv[b-1].y, stv[b].x, stv[b].y)==0){
b--; stv[b].x=v[i].x; stv[b].y=v[i].y;
}
}
g<<b<<"\n";
g<<fixed<<setprecision (12);
for (i=1; i<=b; i++) g<<stv[i].x<<" "<<stv[i].y<<"\n";
}