Pagini recente » Cod sursa (job #2226237) | Cod sursa (job #727062) | Cod sursa (job #2128983) | Cod sursa (job #1306915) | Cod sursa (job #2781957)
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
typedef long double ld;
struct punkt
{
ld x, y;
} low;
bool operator < (punkt a, punkt b)
{
if (a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
ld f(punkt a, punkt b)
{
return (a.x-b.x)*(a.y+b.y);
}
ld f(punkt a, punkt b, punkt c)
{
return f(a, b)+f(b, c)+f(c, a);
}
bool cmp(punkt a, punkt b)
{
return f(low, a, b)>0;
}
const int N=120000+7;
int n;
punkt a[N];
vector<punkt> stk;
void add(punkt a)
{
while ((int) stk.size()>=2 && f(stk[(int) stk.size()-2], stk[(int) stk.size()-1], a)<=0)
stk.pop_back();
stk.push_back(a);
}
int main()
{
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
cin>>n;
for (int i=1; i<=n; i++)
{
cin>>a[i].x>>a[i].y;
}
for (int i=2; i<=n; i++)
if (a[i]<a[1])
swap(a[i], a[1]);
low=a[1];
sort(a+2, a+n+1, cmp);
for (int i=1; i<=n; i++)
{
add(a[i]);
}
add(a[1]);
stk.pop_back();
cout<<(int) stk.size()<<"\n";
for (auto &it : stk)
{
cout<<fixed<<setprecision(12)<<it.x<<" "<<it.y<<"\n";
}
return 0;
}