Cod sursa(job #1892499)

Utilizator markyDaniel marky Data 25 februarie 2017 00:17:03
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <fstream>
#include <stack>
#include <cstdlib>
#include <iomanip>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int nmax = 120005;

struct Point{
double x,y;
}points[nmax];

Point p0;

Point nextToTop(stack<Point> &S){
Point p = S.top();
S.pop();
Point res = S.top();
S.push(p);

return res;
}

void swapp(Point &p1, Point &p2){
Point aux = p1;
p1 = p2;
p2 = aux;
}

double distSq(Point p1, Point p2){
return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
}

int orientation(Point p, Point q, Point r){
double val = (q.y-p.y)*(r.x-q.x)-(q.x-p.x)*(r.y-q.y);

if(val == 0)return 0;

return (val > 0)? 1 : 2;

}

int compare(const void *vp1, const void *vp2){
Point *p1 = (Point *)vp1;
Point *p2 = (Point *)vp2;

double o = orientation(p0,*p1,*p2);

if(o == 0)
    return (distSq(p0,*p2)>=distSq(p0,*p1))? -1 : 1;

return (o == 2)? -1 : 1;
}

void grahamCVhull(Point points[],int n){
    int i;
double ymin = points[0].y; int min = 0;
for(i=1;i<n;i++){
    double y = points[i].y;
    if((y < ymin) || (y == ymin && points[i].x<points[min].x)){
        ymin = points[i].y;
        min = i;
    }
}
swapp(points[0],points[min]);

Point p0 = points[0];
qsort(&points[1], n-1, sizeof(Point), compare);

int m = 1;
for(i=1;i<n;i++){
    while(i < n-1 && orientation(p0,points[i],points[i+1])==0)
        i++;

    points[m]=points[i];
    m++;
}

if(m<3){g<<"IMPOSIBIL\n"; return;}

stack<Point>S;
S.push(points[0]);
S.push(points[1]);
S.push(points[2]);

for(i=3;i<m;i++){
    while(orientation(nextToTop(S), S.top(), points[i])!=2)
        S.pop();

    S.push(points[i]);
}

g<<S.size()<<'\n';

while(!S.empty()){
    Point p = S.top();

    g<<setprecision(12)<<p.x<<" "<<p.y<<'\n';

    S.pop();
}
}

int main(){
    int n,i;
    f>> n;

    for(i=0;i<n;i++)
    f>>points[i].x>>points[i].y;

    g<<fixed;

    grahamCVhull(points,n);

return 0;
}