Pagini recente » Cod sursa (job #1298038) | Cod sursa (job #541105) | Cod sursa (job #2336054) | Cod sursa (job #2901525) | Cod sursa (job #3349170)
#include <bits/stdc++.h>
#define NMAX 120000
#define x first
#define y second
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
pair<double, double> v[NMAX+1];
bool clockwise(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
double area=(b.x-a.x)*(a.y+b.y)+(c.x-b.x)*(b.y+c.y)+(a.x-c.x)*(c.y+a.y);
return area>0;
}
int main()
{
int n;
in >> n;
for(int i=1; i<=n; i++)
{
in >> v[i].x >> v[i].y;
}
sort(v+1, v+n+1);
vector<pair<double, double>> up, down;
pair<double, double> a=v[1], b=v[n];
up.push_back(a);
down.push_back(a);
for(int i=2; i<=n; i++)
{
if(i==n || clockwise(a, v[i], b))
{
while(up.size()>=2 && !clockwise(up[up.size()-2], up[up.size()-1], v[i]))
up.pop_back();
up.push_back(v[i]);
}
if(i==n || !clockwise(a, v[i], b))
{
while(down.size()>=2 && clockwise(down[down.size()-2], down[down.size()-1], v[i]))
down.pop_back();
down.push_back(v[i]);
}
}
out << up.size()+down.size()-2 << "\n";
for(int i=up.size()-1; i>0; i--)
out << fixed << setprecision(6) << up[i].x << " " << up[i].y << "\n";
for(int i=0; i<down.size()-1; i++)
out << fixed << setprecision(6) << down[i].x << " " << down[i].y << "\n";
return 0;
}