Pagini recente » Statistici Niste treapati (CNITV_Diaconu_Popovici_Stoica) | Cod sursa (job #2018757) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1467564)
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <time.h>
#include <bitset>
#include <string>
#include <vector>
#include <math.h>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <limits.h>
#include <algorithm>
#include <deque>
#define nmax 120010
#define mod 1999999973
#define eps 1e-12
using namespace std;
struct date { double x,y; };
int n,i,stiva[nmax],head,p;
date t[nmax]; bool fr[nmax];
stack <int> st;
bool cmp(const date &a,const date &b)
{
if (a.x==b.x) return (a.y<b.y); else
return (a.x<b.x);
}
inline double upper_line(date a,date b,date c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
int main() {
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%lf %lf",&t[i].x,&t[i].y);
sort(t+1,t+n+1,cmp);
stiva[1]=1; stiva[2]=2; head=2; fr[2]=true;
for (i=3,p=1;i>0;i+=(p=(i==n?-p:p))) {
if (fr[i]) continue;
while (head>=2 && upper_line(t[stiva[head-1]],t[stiva[head]],t[i])>=0)
fr[stiva[head--]]=false;
stiva[++head]=i; fr[i]=true;
}
head--;
printf("%d\n",head);
for (i=head;i>=1;i--) printf("%.6lf %.6lf\n",t[stiva[i]].x,t[stiva[i]].y);
return 0;
}