Pagini recente » Cod sursa (job #1086535) | Cod sursa (job #1359492) | Cod sursa (job #2762186) | Cod sursa (job #2889876) | Cod sursa (job #2657726)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<double,double>v[120001];
vector<pair<double,double>>up;
vector<pair<double,double>>down;
vector<pair<double,double>>sus;
vector<pair<double,double>>jos;
bool over(pair<double,double> a,pair<double,double> b,pair<double,double> c)
{
return a.first*b.second+b.first*c.second+c.first*a.second-a.second*b.first-b.second*c.first-a.first*c.second>0;
}
int main()
{
int n;
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>v[i].second>>v[i].first;
}
sort(v+1,v+n+1);
for(int i=1;i<=n;i++)
{
swap(v[i].second,v[i].first);
}
up.push_back(v[1]);
down.push_back(v[1]);
for(int i=2;i<=n;i++)
{
if(over(v[1],v[n],v[i]))
sus.push_back(v[i]);
else jos.push_back(v[i]);
}
for(auto punct:sus)
{
if(up.size()==1)
up.push_back(punct);
else
{
pair<double,double>p2=*up.rbegin();
up.pop_back();
pair<double,double>p1=*up.rbegin();
up.push_back(p2);
while(up.size()>=2&&over(p1,p2,punct))
{
up.pop_back();
p2=*up.rbegin();
up.pop_back();
p1=*up.rbegin();
up.push_back(p2);
}
up.push_back(punct);
}
}
for(auto punct:jos)
{
if(down.size()==1)
down.push_back(punct);
else
{
pair<double,double>p2=*down.rbegin();
down.pop_back();
pair<double,double>p1=*down.rbegin();
down.push_back(p2);
while(down.size()>=2&&!over(p1,p2,punct))
{
down.pop_back();
p2=*down.rbegin();
down.pop_back();
p1=*down.rbegin();
down.push_back(p2);
}
down.push_back(punct);
}
}
fout<<fixed<<setprecision(12);
for(auto punct:down)
fout<<punct.first<<" "<<punct.second<<"\n";
for(int i=up.size()-1;i>0;i--)
fout<<up[i].first<<" "<<up[i].second<<"\n";
}