Pagini recente » Cod sursa (job #2514467) | Cod sursa (job #1641752) | Cod sursa (job #2526707) | Cod sursa (job #988823) | Cod sursa (job #3315851)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef long double ld;
int n;
pair<ld,ld> v[120005];
stack<pair<ld,ld>> s, a, b;
void citire()
{
fin>>n;
for(int i=0; i<n; i++){
pair<ld,ld> p;
fin>>p.first>>p.second;
v[i] = p;
}
}
bool cmp(pair<ld,ld> a, pair<ld,ld> b)
{
if(a.first == b.first) return a.second<b.second;
return a.first<b.first;
}
void parc1(int i, int j, pair<ld,ld> q)
{
if(i>=j) return;
if(s.top() == q){
s.push(v[i]);
parc1(i+1,j,q);
}
else{
pair<ld,ld> aux = s.top();
s.pop();
ld D = (s.top().first*aux.second + aux.first*v[i].second + v[i].first*s.top().second);
D -= (v[i].first*aux.second + aux.first*s.top().second + s.top().first*v[i].second);
if(D>0){
s.push(aux);
s.push(v[i]);
parc1(i+1,j,q);
}
else parc1(i,j,q);
}
}
void parc2(int i, int j, pair<ld,ld> q)
{
if(i<=j) return;
if(s.top() == q){
s.push(v[i]);
parc2(i-1,j,q);
}
else{
pair<ld,ld> aux = s.top();
s.pop();
ld D = (s.top().first*aux.second + aux.first*v[i].second + v[i].first*s.top().second);
D -= (v[i].first*aux.second + aux.first*s.top().second + s.top().first*v[i].second);
if(D>0){
s.push(aux);
s.push(v[i]);
parc2(i-1,j,q);
}
else parc2(i,j,q);
}
}
void afisare()
{
while(!s.empty()){
b.push(s.top());
s.pop();
}
fout<<b.size()<<"\n";
while(!b.empty()){
fout<<b.top().first<<" "<<b.top().second<<"\n";
b.pop();
}
}
int main()
{
citire();
sort(v,v+n,cmp);
s.push(v[0]);
parc1(1,n,s.top());
parc2(n-2,0,s.top());
afisare();
}