Pagini recente » Cod sursa (job #2736457) | Cod sursa (job #2353553) | Cod sursa (job #2787804) | Cod sursa (job #948689) | Cod sursa (job #292196)
Cod sursa(job #292196)
using namespace std;
#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
#define N_MAX 1<<17
typedef vector<int> VI;
typedef pair<db,db> pi;
typedef vector<string> VS;
pi a( mp(1<<30,0) );
int N,last;
vector<pi> V,S,A;
II void scan()
{
freopen(IN,"r",stdin);
freopen(OUT,"w",stdout);
scanf("%d\n",&N);
V.resize(N+1);
S.resize(N+1);
FOR(i,1,N)
scanf("%lf %lf\n",&V[i].f,&V[i].s);
}
II bool comp(pi x,pi y)
{
return (x.f - a.f) * (y.s - a.s) < (y.f - a.f) * (x.s - a.s);
}
II db semn(pi i1,pi i2,pi i3)
{
return (db) i1.f * i2.s + i2.f * i3.s + i3.f * i1.s - i1.s * i2.f - i2.s * i3.f - i3.s * i1.f;
}
II void solve()
{
FOR(i,1,N)
if(V[i] < a)
a = V[i];
S[++last] = a;
FOR(i,1,N)
if(V[i] != a)
A.pb( V[i] );
sort(A.begin(),A.end(),comp);
S[++last] = A[0];
FOR(i,1,(int)A.sz()-1)
{
for(;last >= 2 && semn(S[last-1],S[last],A[i]) > 0;--last);
S[++last] = A[i];
}
printf("%d\n",last);
for(int i=last;i>=1;--i)
printf("%lf %lf\n",S[i].f,S[i].s);
}
int main()
{
scan();
solve();
return 0;
}