Pagini recente » Cod sursa (job #3036726) | Cod sursa (job #2677749) | Cod sursa (job #2833093) | Cod sursa (job #3221586) | Cod sursa (job #2659596)
#include <cmath>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#define EPSILON 0.0000001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point
{
double x, y;
bool operator==(const point other) const
{
return x == other.x && y == other.y;
}
bool operator!=(const point other) const
{
return x != other.x || y != other.y;
}
};
int n;
point a[120005];
vector<point> v1, v2;
bool cmp(point a, point b)
{
if(a.x < b.x)
return true;
if(abs(a.x - b.x) < EPSILON)
return a.y < b.y;
return false;
}
double directie(point a, point b, point c)
{
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
void citire()
{
f>>n;
int pctmin = 0;
for(int i = 0; i<n; i++)
{
f>>a[i].x>>a[i].y;
}
sort(a, a+n, cmp);
}
void rezolvare()
{
v1.push_back(a[0]);
for(int i = 1; i<n; i++)
{
while(v1.size() > 1 && directie(v1[v1.size()-2], v1[v1.size()-1], a[i]) > 0)
{
v1.pop_back();
}
v1.push_back(a[i]);
}
v2.push_back(a[n-1]);
for(int i = n-2; i>=0; i--)
{
while(v2.size() > 1 && directie(v2[v2.size()-2], v2[v2.size()-1], a[i]) > 0)
{
v2.pop_back();
}
v2.push_back(a[i]);
}
}
void afisare()
{
g<<v1.size() + v2.size() - 2<<"\n";
for(int i = 0; i<v1.size() - 1; i++)
{
g<<fixed<<setprecision(6)<<v1[i].x<<" "<<v1[i].y<<"\n";
}
for(int i = 0; i<v2.size() - 1; i++)
{
g<<fixed<<setprecision(6)<<v2[i].x<<" "<<v2[i].y<<"\n";
}
}
int main()
{
citire();
rezolvare();
afisare();
return 0;
}