Cod sursa(job #3268080)

Utilizator bagae123Burlacu Andrei bagae123 Data 13 ianuarie 2025 16:55:19
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include<bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define int double
const signed N=1200005;

struct Point
{
    int x,y;
}v[N],st[N];
int getDet(int X1,int Y1,int X2,int Y2,int X3,int Y3)
{
    return X1*Y2+X2*Y3+X3*Y1-X3*Y2-X1*Y3-X2*Y1;
}
Point Origine;


bool cmp(Point a,Point b)
{
    if (a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}

bool cmp2(Point a,Point b)
{
    return (a.y-Origine.y)*(b.x-Origine.x)>(b.y-Origine.y)*(a.x-Origine.x);
}
signed main()
{
   signed n;
   fin>>n;
   for(signed i=1;i<=n;i++)
   {
       fin>>v[i].x>>v[i].y;
   }
sort(v+1,v+n+1,cmp);
Origine.x=v[1].x;
Origine.y=v[1].y;
signed i;
for (i=1; i<=n; i++)
    cout<<v[i].x<<" "<<v[i].y<<endl;
    cout<<endl;
sort(v+2,v+n+1,cmp2);
for (i=1; i<=n; i++)
    cout<<v[i].x<<" "<<v[i].y<<endl;
signed nr=0;
st[++nr].x=v[1].x;
st[nr].y=v[1].y;
st[++nr].x=v[2].x;
st[nr].y=v[2].y;

for(signed i=3;i<=n;i++)
{
    while(nr>=2&&getDet(st[nr-1].x,st[nr-1].y,st[nr].x,st[nr].y,v[i].x,v[i].y)>0)
    {
        nr--;
    }
    st[++nr].x=v[i].x;
    st[nr].y=v[i].y;
}fout<<nr<<"\n";
for(signed i=1;i<=nr;i++)
{
    fout<<fixed<<setprecision(12)<<st[i].x<<" "<<st[i].y<<"\n";
}



    return 0;
}