Cod sursa(job #1467568)

Utilizator SilviuIIon Silviu SilviuI Data 3 august 2015 16:59:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <time.h>
#include <bitset>
#include <string>
#include <vector>
#include <math.h>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <limits.h>
#include <algorithm>
#include <deque>
#define nmax 120010
#define mod 1999999973
#define eps 1e-12
using namespace std;
struct date { double x,y; };
int n,i,stiva[nmax],head,p;
date t[nmax]; bool fr[nmax];
stack <int> st;
bool cmp(const date &a,const date &b)
{
    if (a.x==b.x) return (a.y<b.y); else
        return (a.x<b.x);
}
inline double upper_line(date a,date b,date c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
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;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=head;i>=1;i--) printf("%.6lf %.6lf\n",t[stiva[i]].x,t[stiva[i]].y);
return 0;
}