Cod sursa(job #2169211)

Utilizator catalinlupCatalin Lupau catalinlup Data 14 martie 2018 14:06:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include<bits/stdc++.h>
#define INFILE "infasuratoare.in"
#define OUTFILE "infasuratoare.out"
#define x first
#define y second
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
typedef pair<double,double> Point;
int N;
vector<Point> points;
Point reper{0,0};
void Read(){
    in>>N;
    for(int i=1;i<=N;i++){
        double cx,cy;
        in>>cx>>cy;
        points.push_back({cx,cy});
    }
}
double CrossProduct(Point P0,  Point P1,  Point P2){
    return (P1.x-P0.x)*(P2.y-P0.y)-(P1.y-P0.y)*(P2.x-P0.x);
}
bool comp( Point A, Point B){
    return CrossProduct(reper,A,B)<0;
}
void AfisPoints(){
    for(auto p:points){
        cout<<p.x<<" "<<p.y<<"\n";
    }
}
void Sortare(){
    int pozPoint=0;
    Point px=points[pozPoint];
    for(int i=1;i<points.size();i++){
        if(points[i].x<px.x){
            px=points[i];
            pozPoint=i;
        }
        else if(points[i].x==px.x&&points[i].y<px.y){
            px=points[i];
            pozPoint=i;
        }
    }
    swap(points[0],points[pozPoint]);
    reper=points[0];
    sort(points.begin()+1,points.end(),comp);
    //AfisPoints();

}
Point Top(vector<Point>&s){
    return s.back();
}
Point Top2(vector<Point>&s){
    return s[s.size()-2];
}
void GrahamScan(){
    vector<Point> st;
    st.push_back(points[0]);
    st.push_back(points[1]);
    for(int i=2;i<points.size();i++){
        while(st.size()>=2&&CrossProduct(Top2(st),Top(st),points[i])>0)
            st.pop_back();
        st.push_back(points[i]);
    }
    out<<st.size()<<"\n";
    for(int i=st.size()-1;i>=0;i--){
        out<<fixed<<setprecision(9)<<st[i].x<<" "<<st[i].y<<"\n";
    }
}
int main(){
    Read();
    Sortare();
    GrahamScan();
    return 0;
}