Cod sursa(job #371338)

Utilizator alexandru92alexandru alexandru92 Data 4 decembrie 2009 21:15:55
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on December 4, 2009, 9:09 PM
 */
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#define pb push_back
#define pr pair< double, double >
#define mk make_pair< double, double >

/*
 *
 */
using namespace std;
pr start, next, now;
vector< pr > v, s;
inline bool cmp( pr p1, pr p2 )
{
    return (p1.first-start.first)*(p2.second-start.second) < (p2.first-start.first)*(p1.second-start.second);
}
inline bool surface( pr p0, pr p1, pr p2 )
{
    double x0=p0.first, y0=p0.second;
    double x1=p1.first, y1=p1.second;
    double x2=p2.first, y2=p2.second;
    return (x0*y1-x2*y1+x1*y2-y2*x0+y0*x2-x1*y0) >= 0 ;
}
int main()
{unsigned int n, i, j, p=0;
    freopen( "cetati.in", "rt", stdin );
    scanf( "%u%lf%lf", &n, &now.first, &now.second );
    start=now;
    v.pb(now);
    for( i=1; i < n; ++i )
    {
        scanf( "%lf%lf", &now.first, &now.second );
        if( now < start )
            start=now, p=i;
        v.pb( now );
    }
    v.erase( v.begin()+p );
    sort( v.begin(), v.end(), cmp );
    s.pb( start );
    s.pb( v[0] );
    s.pb( v[1] );
    for( i=2, n-=1; i < n; ++i )
    {
        for( j=s.size(); j >= 2 && surface( s[j-2], s[j-1], v[i] ) ; --j )
            s.pop_back();
        s.pb( v[i] );
    }
    freopen("cetati.out", "wt", stdout );
    printf( "%u\n", 1+v.size()-s.size() );
   return 0;
}