Cod sursa(job #2988407)

Utilizator BalanelBalan Stefan Balanel Data 4 martie 2023 11:23:44
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n,d[10001],a[100001];
float s;
struct pct{
	double x, y;
}v[120100],st[120100];
double det(pct a, pct b, pct c) {
    return (a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x);
}
int comp(pct a, pct b) {
    return a.y<b.y;
}
int comp1(pct a, pct b) {
    if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int comp2(pct b, pct c) {
    return det(v[1],b,c)<0;
}
int main()
{in>>n;
for(int i=1;i<=n;i++)
    in>>v[i].x>>v[i].y;
sort(v+1,v+n+1,comp1);
st[1]=v[1];
sort(v+2,v+n+1,comp2);
st[2]=v[2];
int k=2;
for(int i=3;i<=n;i++)
    {while(k>2 && det(st[k-1],st[k],v[i])>0)
        k--;
    st[++k]=v[i];
    }
out<<k<<'\n';
for(int i=k;i>=1;i--)
    out<<fixed<<setprecision(6)<<st[i].x<<' '<<st[i].y<<'\n';
return 0;
}