Pagini recente » Cod sursa (job #2096143) | Cod sursa (job #2939239) | Cod sursa (job #13299) | Cod sursa (job #1145758) | Cod sursa (job #3225713)
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <climits>
#define NMAX 120005
#define Point pair<double, double>
#define x first
#define y second
#define EPS 0.00001
#define INF INT_MAX
#define INF INT_MAX
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
vector<Point> pct;
int i;
bool comp(Point, Point);
double dist(Point, Point);
int orientation(Point, Point, Point);
int main()
{
fin >>n;
pct.resize(n);
Point p0; int ind = 0;
p0 = {INF, INF};
for (i = 0; i < n; ++i)
{
fin >>pct[i].x>>pct[i].y;
if (p0.y > pct[i].y)
p0 = pct[i], ind = i;
else
if (p0.y == pct[i].y && p0.x > pct[i].x)
p0 = pct[i], ind = i;
}
swap(pct[0], pct[ind]);
sort(pct.begin()+1, pct.end(), comp);
vector<Point> st;
st.push_back(pct[0]);
st.push_back(pct[1]);
for (i = 2; i < n; ++i)
{
while (st.size() > 2 && orientation(st[st.size()-2], st[st.size()-1], pct[i]) >= 0)
st.pop_back();
st.push_back(pct[i]);
}
fout <<fixed<<setprecision(6)<<st.size()<<'\n';
for (auto crt: st)
fout <<crt.x<<' '<<crt.y<<'\n';
fout.close();
return 0;
}
bool comp(Point a, Point b)
{
int o = orientation(pct[0], a, b);
if (o == 0)
return dist(pct[0], a) < dist(pct[0], b);
return (o < 0);
}
double dist(Point a, Point b)
{
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
int orientation(Point a, Point b, Point c)
{
double o = (b.y-a.y)*(c.x-b.x) - (c.y-b.y)*(b.x-a.x);
if (abs(o) <= EPS)
return 0;
return (o < 0? -1: 1);
}