Pagini recente » Atasamentele paginii jc2012/runda-2/solutii | Cod sursa (job #3360026) | Monitorul de evaluare | Cod sursa (job #3359978) | Cod sursa (job #3360025)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int NMAX=12e4+5;
int n;
complex<double> v[NMAX];
vector<complex<double>> env;
stack<complex<double>> st;
bool cmpr(complex<double> p, complex<double> q)
{
return p.real()<q.real();
}
double ord(complex<double> a, complex<double> b, complex<double> c)
{
complex<double> p=b-a, q=c-a;
return p.real()*q.imag()-p.imag()*q.real();
}
void get_envelope(bool b)
{
int s=b?n:1, sgn=1-2*b;
complex<double> tp(1e10);
for(int i=s;sgn*(i-n-1+s)<=0;i+=sgn)
if(st.empty())
st.push(v[i]);
else if(st.size()==1 && tp.real()>2e9)
tp=v[i];
else
{
while(!st.empty() && ord(v[i], tp, st.top())<=0)
{
tp=st.top();
st.pop();
}
st.push(tp);
tp=v[i];
}
if(!b)
st.push(tp);
while(st.size()>b)
{
env.push_back(st.top());
st.pop();
}
}
int main()
{
in>>n;
for(int i=1;i<=n;i++)
{
double a, b;
in>>a>>b;
v[i]={a, b};
}
sort(v+1, v+n+1, cmpr);
get_envelope(0);
get_envelope(1);
out<<env.size()<<'\n';
out<<fixed<<setprecision(10);
for(auto p:env)
out<<p.real()<<" "<<p.imag()<<'\n';
return 0;
}