Pagini recente » Cod sursa (job #30002) | Cod sursa (job #187027) | Cod sursa (job #1472137) | Cod sursa (job #2343592) | Cod sursa (job #853047)
Cod sursa(job #853047)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
#define PRO "infasuratoare"
void OpenFiles(int EVAL)
{
if(EVAL)
{
char input[100] = PRO, output[100] = PRO;
freopen(strcat(input, ".in"),"r",stdin);
freopen(strcat(output,".out"),"w",stdout);
} else
{
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
}
}
#define MAX 120001
#define INF 0xffffff
#define EPS 1E-8
int n,nlf,nrt;
struct point{ double x,y; }s[MAX],slf[MAX],srt[MAX];
bool cmp(point a,point b){ return a.x < b.x; }
double delta(point a,point b,point c)
{
return a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x;
}
void subsets()
{
sort(s+1,s+n+1,cmp);
slf[++nlf]=srt[++nrt]=s[1];
for(int i=2;i<n;i++)
if( delta(s[1],s[n],s[i]) > 0 )
slf[++nlf] = s[i]; else
srt[++nrt] = s[i];
slf[++nlf]=srt[++nrt]=s[n];
}
void subsetlf()
{
int n=2;
for(int i=3;i<=nlf;i++)
{
while(n>=2 && delta(slf[n-1],slf[i],slf[n]) - EPS < 0)n--;
slf[++n] = slf[i];
}
nlf = n;
}
void subsetrt()
{
int n=2;
for(int i=3;i<=nrt;i++)
{
while(n>=2 && delta(srt[n-1],srt[i],srt[n]) + EPS > 0)n--;
srt[++n] = srt[i];
}
nrt = n;
}
int main(int argv,char *args[])
{
OpenFiles(argv==0);
// start
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf %lf",&s[i].x,&s[i].y);
subsets();
subsetlf();
subsetrt();
printf("%d\n",nlf+nrt-2);
for(int i=nlf;i>0;i--)printf("%lf %lf\n",slf[i].x,slf[i].y);
for(int i=2;i<nrt;i++)printf("%lf %lf\n",srt[i].x,srt[i].y);
return 0;
}