Pagini recente » Cod sursa (job #893333) | Cod sursa (job #1954115) | Cod sursa (job #1926613) | Cod sursa (job #218982) | Cod sursa (job #2659615)
#define NMAX 120005
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point{
double x = 0, y = 0;
}P[NMAX];
int n;
vector<point> v1, v2;
bool cmp(point A, point B)
{
if(A.x < B.x || A.x == B.x && A.y < B.y)
return 1;
return 0;
}
void read()
{
f>>n;
for(int i = 1; i <= n; ++i)
f>>P[i].x>>P[i].y;
sort(P+1, P+n+1, cmp);
}
double determinant(point P1, point P2, point P3)
{
return (P2.x - P1.x)*(P3.y - P1.y) - (P2.y - P1.y)*(P3.x - P1.x);
}
void write()
{
g<<v1.size() + v2.size() - 2<<'\n';
for(auto &v:v1)
g<<fixed<<setprecision(6)<<v.x<<" "<<v.y<<"\n";
for(int i = 1; i < v2.size()-1; ++i)
g<<fixed<<setprecision(6)<<v2[i].x<<" "<<v2[i].y<<"\n";
}
void solve()
{
v1.push_back(P[1]);
v1.push_back(P[2]);
for(int i = 3; i <= n; ++i)
{
if(v1.size() <= 1)
v1.push_back(P[i]);
else{
while(v1.size() > 1 && determinant(v1[v1.size()-2], v1[v1.size()-1], P[i]) < 0)
v1.pop_back();
v1.push_back(P[i]);
}
}
v2.push_back(P[n]);
v2.push_back(P[n-1]);
for(int i = n-2; i >= 1; --i)
{
if(v1.size() <= 1)
v2.push_back(P[i]);
else{
while(v1.size() > 1 && determinant(v2[v2.size()-2], v2[v2.size()-1], P[i]) < 0)
v2.pop_back();
v2.push_back(P[i]);
}
}
}
int main()
{
read();
solve();
write();
return 0;
}