Pagini recente » Cod sursa (job #1296547) | Cod sursa (job #846918) | Cod sursa (job #2353889) | Cod sursa (job #2964543) | Cod sursa (job #2523964)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
struct Point
{
double x,y;
} a[120001];
int head = 1;
void Read()
{
double x,y;
f>>n;
for(int i=0;i<n;++i)
{
f>>x>>y;
a[i].x = x;
a[i].y = y;
}
f.close();
}
double cross_product(Point A,Point B,Point C)
{
return (C.y - A.y) * (B.x - A.x) - (B.y - A.y) * (C.x - A.x);
}
bool compare(Point B,Point C)
{
return cross_product(a[0],B,C) < 0;
}
void Sort()
{
int pos = 0;
for(int i=1;i<n;++i)
if(a[i].x < a[pos].x)
pos = i;
else if(a[i].x == a[pos].x && a[i].y < a[pos].y)
pos = i;
swap(a[0],a[pos]);
sort(a+1,a+n,compare);
}
Point s[120001];
void convex_hull()
{
Sort();
s[0] = a[0];
s[1] = a[1];
for(int i=2;i<n;++i)
{
while(head >= 2 && cross_product(s[head-1],s[head],a[i]) > 0)
--head;
s[++head] = a[i];
}
}
void Print()
{
g<<setprecision(12)<<fixed;
g<<head+1<<'\n';
for(int i=head;i>=0;--i)
g<<s[i].x<<" "<<s[i].y<<'\n';
g.close();
}
int main()
{
Read();
convex_hull();
Print();
return 0;
}