Cod sursa(job #3168576)

Utilizator AndreidreiGresoiu Liviu-Andrei Andreidrei Data 12 noiembrie 2023 19:02:40
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 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 998244353ll
#define nmax 100004
using namespace std;
typedef long long ll;
ifstream in("infasuratoare.in");
//ofstream out("infasuratoare.out");
//FILE *fin=fopen("ghicit.in","r");
FILE *fout=fopen("ghicit.out","w");
ll n,i,j,k,l,b,w,x,y,z,o[nmax];pair<double,double>p[nmax];
int main()
{
in>>n;
for(i=0;i<n;i++)in>>p[i].f>>p[i].s;
forq(i,0,n)if(p[i].s<p[w].s||(p[i].s==p[w].s&&p[i].f<p[w].f))w=i;
//printf("%d %d",p[w].f,p[w].s);
swap(p[w],p[0]);
sort(p+1,p+n,[](pair<ll,ll>a,pair<ll,ll>b){return (b.f-p[0].f)*(a.s-p[0].s)-(a.f-p[0].f)*(b.s-p[0].s)<0;});
//forq(i,0,n)printf("%d %d\n",p[i].f,p[i].s);
o[0]=0,o[1]=1,l=1;
for(i=2;i<n;i++)
{
    while(p[o[l-1]].f*(p[o[l]].s-p[i].s)+p[o[l]].f*(p[i].s-p[o[l-1]].s)+p[i].f*(p[o[l-1]].s-p[o[l]].s)<=0)l--;
    o[++l]=i;
}
//printf("PA\n");forq(i,0,l+1)printf("%d %d\n",p[o[i]].f,p[o[i]].s);
fprintf(fout,"%d\n",l+1);
forq(i,0,l+1)fprintf(fout,"%f %f\n",p[o[i]].f,p[o[i]].s);
}