Pagini recente » Cod sursa (job #1941465) | Cod sursa (job #18657) | Cod sursa (job #1029361) | Cod sursa (job #1423106) | Cod sursa (job #3225685)
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#define NMAX 120005
#define Point pair<double, double>
#define x first
#define y second
#define CLOCKWISE 1
#define COL 0
#define COUNTER -1
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
Point pct[NMAX];
int i;
bool comp(Point, Point);
int orientation(Point, Point, Point);
int main()
{
fin >>n;
for (i = 1; i <= n; ++i)
fin >>pct[i].x>>pct[i].y;
swap(pct[1], *min_element(pct+2, pct+n+1));
sort(pct+2, pct+n+1, comp);
vector<Point> st;
st.push_back(pct[1]);
st.push_back(pct[2]);
for (i = 3; 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]);
}
reverse(st.begin(), st.end());
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)
{
return (orientation(pct[1], a, b) == COUNTER);
}
int orientation(Point a, Point b, Point c)
{
double aux = (b.y-a.y)*(c.x-b.x) - (c.y-b.y)*(b.x-a.x);
if (aux == 0)
return COL;
return (aux < 0? COUNTER: CLOCKWISE);
}