Pagini recente » Borderou de evaluare (job #535723) | Cod sursa (job #2044007) | Cod sursa (job #624468) | Cod sursa (job #1637797) | Cod sursa (job #3314981)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
vector<pair<double,double>> v;
stack<pair<double,double>> S;
void citire()
{
fin>>n;
pair<double,double> P;
for(int i=0; i<n; i++){
fin>>P.first>>P.second;
v.push_back(P);
}
}
void qvick(int st, int dr)
{
if(st>=dr) return;
int m = (st+dr)/2;
pair<double,double> aux = v[st];
v[st] = v[m];
v[m] = aux;
int i=st, j=dr, d=0;
while(i<j){
if(v[i].first>v[j].first){
auto aux = v[i];
v[i] = v[j];
v[j] = aux;
d = 1-d;
}
else if(v[i].first==v[j].first && v[i].second>v[j].second){
auto aux = v[i];
v[i] = v[j];
v[j] = aux;
d = 1-d;
}
i += d;
j -= 1-d;
}
qvick(st,i-1);
qvick(i+1,dr);
}
void parc(int i, int d, pair<double,double> q)
{
if((i>=n && d==1)||(i<=-1 && d==-1)) return;
if(S.top() == q){
S.push(v[i]);
parc(i+d,d,q);
}
else{
auto aux = S.top();
S.pop();
double det = (S.top().first*aux.second + aux.first*v[i].second + v[i].first*S.top().second);
det -= (v[i].first*aux.second + aux.first*S.top().second + S.top().first*v[i].second);
if(det<0){
S.push(aux);
S.push(v[i]);
parc(i+d,d,q);
}
else parc(i,d,q);
}
}
int main()
{
citire();
qvick(0,n-1);
S.push(v[0]);
pair<double,double> q;
q = v[0];
parc(1,1,q);
q = S.top();
parc(n-2,-1,q);
fout<<S.size()-1<<'\n';
while(S.size()>1){
fout<<S.top().first<<' '<<S.top().second<<'\n';
S.pop();
}
}