Pagini recente » Cod sursa (job #2297206) | ONIS 2015, Solutii Runda 1 | Cod sursa (job #277875) | Cod sursa (job #1963321) | Cod sursa (job #406413)
Cod sursa(job #406413)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct point{ double x,y; double u;};
bool cmp(point a,point b) {
return a.u < b.u;
}
int isleft(point c, point b, point a)
{
double det = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
if(det>0) return 1;
return 0;
}
int main()
{
ifstream f("infasuratoare.in");
ofstream f2("infasuratoare.out");
int N;
f>>N;
vector<point> p;
for(int i=0;i<N; ++i)
{
double x,y;
f>>x>>y;
point pp;
pp.x = x;
pp.y = y;
p.push_back(pp);
}
int indmin = 0;
for(int i=1;i<N;++i)
{
if((p[indmin].x<p[i].x) || (p[indmin].x==p[i].x && p[indmin].y>p[i].y))
{
indmin = i;
}
}
vector<point> st;
for(int i=0; i<N; i++)
{
p[i].u = atan2((p[i].y - p[indmin].y),(p[i].x - p[indmin].x));
}
sort(p.begin(), p.end(), cmp);
//for(int i=1; i<N; ++i) cout<<p[i].x<<" "<<p[i].y<<" "<<p[i].u<<"\n";
st.push_back(p[0]);
st.push_back(p[1]);
int i=2;
while(i<N)
{
if(isleft(p[i],st[st.size()-1],st[st.size()-2]))
{
st.push_back(p[i]);
++i;
}
else st.pop_back();
}
f2 << st.size() << endl;
for(int i=0; i<st.size(); ++i) f2<<st[i].x<<" "<<st[i].y<<"\n";
return 0;
}