Pagini recente » Cod sursa (job #1715983) | Cod sursa (job #1653096) | Monitorul de evaluare | Diferente pentru problema/bitconnect intre reviziile 48 si 16 | Cod sursa (job #292212)
Cod sursa(job #292212)
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 semn(i1,i2,i3) (db) X[i1] * Y[i2] + X[i2] * Y[i3] + X[i3] * Y[i1] - Y[i1] * X[i2] - Y[i2] * X[i3] - Y[i3] * X[i1]
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
#define N_MAX 1<<17
int N,last,pi;
db X[N_MAX],Y[N_MAX];
int A[N_MAX],S[N_MAX];
II void scan()
{
freopen(IN,"r",stdin);
freopen(OUT,"w",stdout);
scanf("%d\n",&N);
FOR(i,1,N)
scanf("%lf %lf\n",&X[i],&Y[i]);
}
II bool comp(int i,int j)
{
return (X[i] - X[pi]) * (Y[j] - Y[pi]) < (X[j] - X[pi]) * (Y[i] - Y[pi]);
}
II void solve()
{
X[0] = Y[0] = 1<<30;
FOR(i,1,N)
if(X[i] < X[pi] || (X[i] == X[pi] && Y[i] < Y[pi]) )
pi = i;
FOR(i,1,N)
if(i != pi)
A[++A[0]] = i;
sort(A+1,A+A[0]+1,comp);
S[++last] = pi;
S[++last] = A[0];
FOR(i,1,A[0])
{
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",X[ S[i] ],Y[ S[i] ]);
}
int main()
{
scan();
solve();
return 0;
}