Cod sursa(job #3195721)

Utilizator vladdobro07vladdd vladdobro07 Data 21 ianuarie 2024 15:52:48
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax=12e4;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct point {
        double x,y;
};
vector<point>hull;
vector<point>pts(nmax+3);
int n;
int findStartPoint() {
        int rez=0;
        double minny=1e9,maxxx=0;
        for(int i=1; i<n; i++) {
                if(pts[i].y<minny) {
                        minny=pts[i].y;
                        maxxx=pts[i].x;
                        rez=i;
                } else if(pts[i].y==minny) {
                        if(pts[i].x>maxxx) {
                                maxxx=pts[i].x;
                                rez=i;
                        }
                }
        }
        return rez;
}
double orient(point a,point b,point c) {
        return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}
bool cmp(point a,point b) {
        return orient(pts[0],a,b)<0;
}
void createConvexHull() {
        hull.push_back(pts[0]);
        hull.push_back(pts[1]);
        for(int i=2; i<n; i++) {
                while(hull.size()>=2&&orient(hull[hull.size()-2],hull[hull.size()-1],pts[i])>=0)
                        hull.pop_back();
                hull.push_back(pts[i]);
        }
}
int main() {
        cin>>n;
        for(int i=0; i<n; i++)
                cin>>pts[i].x>>pts[i].y;
        swap(pts[0],pts[findStartPoint()]);
        sort(pts.begin()+1,pts.begin()+n,cmp);
        createConvexHull();

        cout << setprecision(6) << fixed;

        cout<<hull.size()<<"\n";
        for(auto punctuletz:hull){
          cout<<punctuletz.x<<" "<<punctuletz.y<<"\n";
        }
        return 0;
}