Cod sursa(job #3124098)

Utilizator Paul281881818818181991919191881818Draghici Paul Paul281881818818181991919191881818 Data 26 aprilie 2023 21:43:33
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.62 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <stack>
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
int n;
class Point{
public:
    int x = 0, y = 0;
    Point() {};
    Point(int x, int 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 int 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);
}
int compare(const void* vp1, const void* vp2){
    Point* p1 = (Point*) vp1;
    Point* p2 = (Point*) vp2;
    int o = orientation(p0, *p1, *p2);
    if(o == 0)
        return (dist(p0, *p2) >= dist(p0, *p1)) ? -1 : 1;
    return ((o == 2)? -1 : 1);
}
int main(){
    fin >> n;
    for(int x, y, i = 0; i < n; i++){
        fin >> x >> y;
        Point point(x, y);
        points.push_back(point);
    }
    int ymin = points[0].y, min = 0;
    for(int i = 1; i < n; i++){
        if(ymin > points[i].y || (ymin == points[i].y && points[i].x < points[min].x)){
            ymin = points[i].y, min = i;
        }
    }
    
    swap(points[0], points[min]);
    p0 = points[0];
    qsort(&points[1], n - 1, sizeof(Point), compare);
    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++;
    }
    if(m < 3)
        return 0;
    std::stack<Point> S;
    S.push(points[0]);
    S.push(points[1]);
    S.push(points[2]);
    for(int i = 3; i < m; i++){
        while(S.size() > 1 && orientation(nextToTop(S), S.top(), points[i]) != 2)
            S.pop();
        S.push(points[i]);
    }
    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 << (*it).x << " " << (*it).y << "\n";
    }
}