Cod sursa(job #3126401)

Utilizator Paul281881818818181991919191881818Draghici Paul Paul281881818818181991919191881818 Data 6 mai 2023 16:42:59
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.18 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <stack>
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
int n;
class Point{
public:
    long double x = 0, y = 0;
    Point() {};
    Point(long double x, long double y) : x(x), y(y) {};
    friend std::ostream& operator <<(std::ostream& fout, const Point& point){
        fout << "(" << point.x << ", " << point.y << ")";
        return fout;
    }
};
std::vector<Point> points;

Point p0;
Point nextToTop(std::stack<Point>& S){
    Point top = S.top();
    S.pop();
    Point next = S.top();
    S.push(top);
    return next;
}
void swap(Point& P, Point& Q){
    Point temp;
    temp = P;
    P = Q;
    Q = temp;
}
inline long double dist(const Point& P, const Point& Q){
    return (Q.x - P.x) * (Q.x - P.x) + (Q.y - P.y) * (Q.y - P.y);
}
int orientation(const Point& P, const Point& Q, const Point& R){
    int alpha = (Q.y - P.y) * (R.x - Q.x) - (R.y - Q.y) * (Q.x - P.x);
    if(alpha == 0)
        return 0;
    return ((alpha > 0) ? 1 : 2);
}
bool compare(const Point& p1, const Point& p2){
    int o = orientation(p0, p1, p2);
    if(o == 0)
        return (dist(p0, p2) >= dist(p0, p1)) ? true : false;
    return ((o == 2)? true : false);
}
bool ToLeft ( const Point & A, const Point & B, const Point & C )
{
    return (( 1LL * B.y - A.y ) * ( C.x - B.x ) < (1LL *C.y - B.y ) * ( B.x - A.x ));
}

bool comp( const Point & B, const Point & C )
{
    return ToLeft( points[1], B, C );
}
int main(){
    fin >> n;
    for(int  i = 0; i < n; i++){
        long double x, y;
        fin >> x >> y;
        Point point(x, y);
        points.push_back(point);
    }
    long double xmin = points[0].x;int min = 0;
    for(int i = 1; i < n; i++){
        if(xmin > points[i].x || (xmin == points[i].x && points[i].y < points[min].y)){
            xmin = points[i].x, min = i;
        }
    }
    
    swap(points[0], points[min]);
    p0 = points[0];
    std::sort(points.begin() + 1, points.end(), compare);
    /*for(auto it : points){
        std::cout << it << "\n";
    }*/
    /*int m = 1;
    for(int i = 1; i < n; i++){
        while(i < n - 1 && orientation(p0, points[i], points[i + 1]) == 0){
            i ++;
        }
        points[m] = points[i];
        m++;
    }*/
    
    std::stack<Point> S;
    S.push(points[0]);
    S.push(points[1]);
    S.push(points[2]);
    for(int i = 3; i < n; i++){
        //std::cout << nextToTop(S) << " " << S.top() << " " << points[i] << orientation(nextToTop(S), S.top(), points[i]) <<" " << "\n";
        while(S.size() > 1 && orientation(nextToTop(S), S.top(), points[i]) != 2){
            S.pop();
        }
        S.push(points[i]);
        //std::cout << points[i] << "\n";
    }
    std::vector<Point> result;
    while(!S.empty()){
        Point p = S.top();
        result.push_back(p);
        S.pop();
    }
    fout << result.size() << "\n";
    for(std::vector<Point>::reverse_iterator it = result.rbegin(); it != result.rend(); it ++){
        fout << std::fixed << std::setprecision(6) << (*it).x << " " << (*it).y << "\n";
    }
}