Pagini recente » Cod sursa (job #381931) | Cod sursa (job #3163896) | Cod sursa (job #1601508) | Cod sursa (job #3156846) | Cod sursa (job #409636)
Cod sursa(job #409636)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdio>
using namespace std;
struct point{ double x,y; double u;};
bool cmp(point a,point b) {
return a.u < b.u || (a.u == b.u && a.x < b.x);
}
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()
{
FILE* f = fopen("infasuratoare.in","r");
FILE* f2 = fopen("infasuratoare.out","w");
int N;
fscanf(f,"%d",&N);
vector<point> p;
for(int i=0;i<N; ++i)
{
point pp;
fscanf(f,"%lf %lf",&(pp.x),&(pp.y));
p.push_back(pp);
}
point pRef;
pRef.x = 10;
pRef.y = 0;
vector<point> st;
for(int i=0; i<N; i++)
{
p[i].u = atan2((p[i].y - pRef.y),(p[i].x - pRef.x));
}
sort(p.begin(), p.end(), cmp);
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;
}
}
st.push_back(p[indmin]);
st.push_back(p[(indmin+1)%N]);
int i=(indmin+2)%N;
int T = i-1>0 ? i-1 : N-1;
while(i!=T)
{
if(i>(indmin+1)%N) T = (indmin+1)%N;
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; }
}
fprintf(f2,"%d\n",st.size()-1);
for(int i=1; i<st.size(); ++i)
{
fprintf(f2,"%.6g %.6g\n",st[i].x,st[i].y);
}
return 0;
}