Cod sursa(job #2936213)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 8 noiembrie 2022 12:12:21
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#define nmax 120003
//#define float double
#define inf FLT_MAX
#define pi 3.14159
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct pt{
    float x,y;
};

float pant(const pt &a, const pt &b)
{
    return (b.x-a.x)/(b.y-a.y);
}

pt st;
pt s[nmax];
bool cmp(const pt &a, const pt &b)
{
    return pant(st,a)>pant(st,b);
}

float cross(const pt &a, const pt &b, const pt  &c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a,y)*(c.x-a.x);
}

int n;
pt stk[nkmax];
int k;

int main()
{
    f>>n;
    st.x=inf;
    st.y=inf;
    for(int i=0;i<n;i++)
    {
        f>>s[i].x>>s[i].y;
        if(s[i].x<st.x) st=s[i];
        else if(s[i].x==st.x&&s[i].y<st.y) st=s[i];
    }
    sort(s,s+n,cmp);
    for(auto e:s)
    {
        stk[k++]=e;
        while(k>3&&cross(stk[k-3],stk[k-2],stk[k-1])>0) k--;
    }
    for(int i=0;i<k;i++)
    {
        g<<fixed<<setprecision(6)<<stk[i].x<<','<<stk[i].y<<'\n';
    }
    

    return 0;
}