Pagini recente » Cod sursa (job #68258) | Cod sursa (job #386206) | Cod sursa (job #454875) | Cod sursa (job #1966635) | Cod sursa (job #1368280)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define punct pair<double,double>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int N,i,j;
vector<punct> v;
bool ec(punct a,punct b,punct c)
{
double A=a.y - b.y;
double B=b.x - a.x;
double C=b.y * a.x - a.y * b.x;
return (A * c.x + B * c.y + C > 0);
}
double a,b;
int main()
{
f>>N;
for(i=1;i<=N;++i)
{
f>>a>>b;
v.push_back(make_pair(a,b));
}
sort(v.begin(),v.end());
vector<punct> st,hull;
st.push_back(v[0]);
for(i=1;i<N;++i)
{
if(ec(v[0],v[N-1],v[i]) || i == N - 1)
{
while(st.size()>=2 && !ec(st[st.size()-2],v[i],st.back()))
st.pop_back();
st.push_back(v[i]);
}
}
hull=st;hull.pop_back();
st.clear();
st.push_back(v[N-1]);
for(i=N-1;i>=0;--i)
{
if(ec(v[N-1],v[0],v[i]) || i == 0)
{
while(st.size()>=2 && !ec(st[st.size()-2],v[i],st.back()))
st.pop_back();
st.push_back(v[i]);
}
}
for(i=0;i<st.size();++i)
hull.push_back(st[i]);
g<<hull.size()-1<<'\n';
for (i=hull.size()-2;i>=0;--i)
g<<fixed<<setprecision(6)<<hull[i].first<<" "<<hull[i].second<<'\n';
return 0;
}