Pagini recente » Cod sursa (job #352825) | Cod sursa (job #1470947) | Cod sursa (job #2233558) | Cod sursa (job #2726536) | Cod sursa (job #371338)
Cod sursa(job #371338)
/*
* 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;
}