Pagini recente » Cod sursa (job #1627761) | Cod sursa (job #2267736) | Cod sursa (job #2618731) | Cod sursa (job #706683) | Cod sursa (job #1119571)
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 120001
struct punct{
double x, y;
bool d;
}P[MAX];
bool f(punct a , punct b)
{
if(a.y == b.y)return a.x < b.x;
return a.y < b.y;
}
int N , k , st[MAX];
bool det(punct p1 , punct p2 , punct p3 )
{
return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p2.y*p3.x-p3.y*p1.x-p2.x*p1.y > 0;
}
void read();
void solve();
void write();
void add(int x);
int main()
{
read();
solve();
write();
return 0;
}
void read()
{
freopen("infasuratoare.in" , "r" , stdin );
scanf("%d" , &N );
for(int i = 1 ; i<= N ; ++i )
scanf("%lf%lf" , &P[i].x , &P[i].y);
}
void solve()
{
sort(P+1,P+N+1 , f);
for(int i = 1 ; i<= N ; ++i )
add(i);
for(int i = N ; i ; i--)
if(!P[i].d)add(i);
if(!det(P[st[k-1]],P[st[k]],P[st[1]]))k--;
}
void write()
{
freopen("infasuratoare.out" , "w" , stdout );
printf("%d\n" , k);
for(int i = 1 ; i<=k ; ++i )
printf("%lf %lf\n" , P[st[i]].x , P[st[i]].y );
/* for(int i = 1 ; i<= N ; ++i )
printf("%f %f\n" , P[i].x , P[i].y );*/
}
void add(int x)
{
if(k < 2){
st[++k] = x;
P[x].d = 1;}
else
{
st[++k] = x;
P[x].d = 1;
while(k > 2 && !det(P[st[k-2]],P[st[k-1]],P[st[k]]))
{
P[st[k-1]].d = 0;
st[k-1] = st[k];
k--;
}
}
}