Cod sursa(job #1476146)

Utilizator SilviuIIon Silviu SilviuI Data 24 august 2015 15:11:20
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <stdio.h>
#include <algorithm>
#define nmax 120010
using namespace std;
struct date { double x,y; };
int n,i,j,stiva[nmax],head=0;
bool fr[nmax];
date t[nmax];
inline double upper_line(date a,date b,date c)
{
    return (a.x*b.y+a.y*c.x+b.x*c.y-c.x*b.y-a.y*b.x-c.y*a.x);
}
bool cmp(const date &a,const date &b)
{
    if (a.x==b.x) return (a.y<b.y); else
        return (a.x<b.x);
}
int main() {
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%lf %lf",&t[i].x,&t[i].y);
sort(t+1,t+n+1,cmp);
stiva[1]=1; stiva[2]=2; head=2; fr[2]=true;
for (i=3;i<=n;i++) {
    if (fr[i]) continue;
    while (head>=2 && upper_line(t[stiva[head-1]],t[stiva[head]],t[i])<=0)
       fr[stiva[head]]=false,head--;
    head++; stiva[head]=i; fr[i]=true;
}
for (i=n-1;i>=1;i--) {
    if (fr[i]) continue;
    while (head>=2 && upper_line(t[stiva[head-1]],t[stiva[head]],t[i])<=0)
       fr[stiva[head]]=false,head--;
    head++; stiva[head]=i; fr[i]=true;
}
head--;
printf("%d\n",head);
for (i=1;i<=head;i++) printf("%lf %lf\n",t[stiva[i]].x,t[stiva[i]].y);
return 0;
}