Pagini recente » Cod sursa (job #380601) | Statistici Florin Citu (florincitu) | Cod sursa (job #647895) | Sandbox (cutiuţa cu năsip) | Cod sursa (job #2953841)
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int NMAX = 12e2;
struct ura
{
double x, y;
} v[NMAX+1];
vector<ura> st;
int pmin;
double trig(ura a, ura b, ura c)
{
return ((c.y-b.y)*(b.x-a.x) - (b.y-a.y)*(c.x-b.x)) > 0;
}
bool cmp(ura a, ura b)
{
return trig(a, v[pmin], b) > 0;
}
int main()
{
int n;
cin>>n;
v[0].y = 1e9;
for(int i=1; i<=n; i++)
{
cin>>v[i].x>>v[i].y;
if(v[pmin].y > v[i].y)
pmin = i;
}
sort(v+1, v+n+1, cmp);
st.push_back(v[1]);
st.push_back(v[2]);
for(int i=3; i<=n; i++)
{
int l = st.size();
while(st.size() > 0 && 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=st.size()-1; i>=0; i--)
cout<<st[i].x<<" "<<st[i].y<<"\n";
}