Cod sursa(job #3216444)

Utilizator AndreidreiGresoiu Liviu-Andrei Andreidrei Data 17 martie 2024 10:08:21
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 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 fto(i,ii,n)for(i=ii;i<n;i++)
#define f first
#define s second
#define mod 1000003ll
#define nmax 200003
#define lim 351
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
//ifstream in("password.in");
//ofstream out("password.out");
FILE *fin=fopen("infasuratoare.in","r");
FILE *fout=fopen("infasuratoare.out","w");
int n,m,i,j,k,l;
struct p{double x,y,u;}a[nmax],*c[nmax];
int main()
{
fscanf(fin,"%d",&n);
fto(i,0,n){
    fscanf(fin,"%lf%lf",&a[i].x,&a[i].y);
    if(a[i].x<a[k].x||(a[i].x==a[k].x&&a[i].y<a[k].y))k=i;
}
if(k)swap(a[k],a[0]);
fto(i,1,n)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;});
c[0]=a,c[1]=a+1,l=1;
fto(i,2,n){
    while(l&&c[l]->x*(c[l-1]->y-a[i].y)+c[l-1]->x*(a[i].y-c[l]->y)+a[i].x*(c[l]->y-c[l-1]->y)>0)l--;
    c[++l]=a+i;
}
fprintf(fout,"%d",l+1);
fto(i,0,l+1)fprintf(fout,"\n%lf %lf",c[i]->x,c[i]->y);
}