Cod sursa(job #2724084)

Utilizator alexboldasAlex Boldas alexboldas Data 16 martie 2021 13:42:49
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include<fstream>
#include<vector>
#include<cmath>
#include<algorithm>
#define pi 3.14159265359
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct qwerty{
    double x,y;
}a,mn;
int i,j,n,m;
vector <qwerty>x;
vector <qwerty>z;
bool unghi(qwerty a,qwerty b,qwerty c){
    double arie = (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    if(arie<0)
        return true;
    return false;
}
void pr1(){
    z.push_back(mn);
    z.push_back(x[0]);
    for(int i=1,size=x.size();i<size;i++){
        while(!unghi(z[z.size()-1],z[z.size()-2],x[i]))
            z.pop_back();
        z.push_back(x[i]);

    }
}
bool cum(qwerty a,qwerty b){
    return atan2(mn.y-a.y,mn.x-a.x)<atan2(mn.y-b.y,mn.x-b.x);
}
int main(){
    fin>>n;
    fin>>mn.x>>mn.y;
    for(i=2;i<=n;i++){
        fin>>a.x>>a.y;
        if(a.y==mn.y)
            if(a.x<mn.x)
                x.push_back(mn),mn=a;
            else
                x.push_back(a);
        else
            if(a.y<mn.y)
                x.push_back(mn),mn=a;
            else
                x.push_back(a);
    }
    sort(x.begin(),x.end(),cum);
    pr1();
    fout<<z.size()<<'\n';
    for(i=0;i<z.size();i++)
        fout<<z[i].x<<' '<<z[i].y<<'\n';
    return 0;
}