Pagini recente » Cod sursa (job #3199394) | Cod sursa (job #2049784) | Cod sursa (job #2630795) | Cod sursa (job #992634) | Cod sursa (job #408008)
Cod sursa(job #408008)
#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;
}
double dist(point a,point b)
{
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
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;
if(det == 0 && dist(a,c)>dist(a,b)) return 0;
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;
int T = 1;
while(i!=T)
{
if(i>2) T = 2;
i = i%N;
if(st.size()<2) { st.push_back(p[i]); continue; }
int d = isleft(p[i],st[st.size()-1],st[st.size()-2]);
if(d == 1) { st.push_back(p[i++]); continue; }
if(d == 0) { st.pop_back(); continue; }
}
f2<<st.size()-2<<"\n";
for(int i=2; i<st.size(); ++i) f2<<st[i].x<<" "<<st[i].y<<"\n";
return 0;
}