Cod sursa(job #3156300)

Utilizator AndreidreiGresoiu Liviu-Andrei Andreidrei Data 11 octombrie 2023 10:06:15
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
#include <cstring>
#include <cstdio>
#pragma GCC optimize ("O3")
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?(a):(b))
#define bmax(a,b)((a>b)?(a):(b))
#define bminify(a,b)a=bmin(a,b)
#define bmaxify(a,b)a=bmax(a,b)
#define forq(i,ii,n)for(i=ii;i<n;i++)
#define f first
#define s second
#define mod 777777777ll
#define nmax 120001
using namespace std;
typedef long long ll;
//ifstream in("ghicit.in");
//ofstream out("cuba.out");
FILE *fin=fopen("infasuratoare.in","r");
FILE *fout=fopen("infasuratoare.out","w");
struct p{int i;double x,y,u;}a[nmax];
int n,i,j,k,l;p*q[nmax+1];
int main()
{
fscanf(fin,"%d",&n);
for(i=0;i<n;i++)
{
    fscanf(fin,"%lf%lf",&a[i].x,&a[i].y);
    if(a[k].x>a[i].x||(a[k].x==a[i].x&&a[k].y>a[i].y))
        k=i;
}
if(k)swap(a[k],a[0]);
for(i=1;i<n;i++)a[i].u=(a[i].y-a[0].y)/(a[i].x-a[0].x);
sort(a+1,a+n,[](p a,p b){return a.u<b.u;});
q[0]=a,q[1]=a+1,l=1;
for(i=2;i<n;i++)
{
    while(l&&q[l-1]->x*(q[l]->y-a[i].y)+q[l]->x*(a[i].y-q[l-1]->y)+a[i].x*(q[l-1]->y-q[l]->y)<0)--l;
    q[++l]=a+i;
}
fprintf(fout,"%d\n",l+1);
for(i=0;i<=l;i++)fprintf(fout,"%.6lf %.6lf\n",q[i]->x,q[i]->y);
}