Pagini recente » Cod sursa (job #2720881) | Cod sursa (job #2098648) | Cod sursa (job #1765520) | Cod sursa (job #388705) | Cod sursa (job #2955552)
#include<fstream>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int NMAX = 120000;
struct ura
{
double x, y;
} v[NMAX+1];
vector<ura> st;
int pmin;
double trig(ura a, ura b, ura c)
{
return (b.y-a.y)*(c.x-b.x) - (c.y-b.y)*(b.x-a.x);
}
bool cmp(ura a, ura b)
{
return trig(v[0], a, b) < 0;
}
int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>v[i].x>>v[i].y;
if(v[pmin].y > v[i].y || (v[pmin].y == v[i].y && v[i].x < v[pmin].y))
pmin = i;
}
swap(v[0], v[pmin]);
sort(v+1, v+n, cmp);
st.push_back(v[0]);
st.push_back(v[1]);
for(int i=2; i<n; i++)
{
int l = st.size();
while(st.size() >= 2 && trig(st[l-2], st[l-1], v[i]) >= 0)
{
l--;
st.pop_back();
}
st.push_back(v[i]);
}
cout<<st.size()<<'\n';
for(int i=0; i<st.size(); i++)
cout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
}