Pagini recente » Istoria paginii runda/simulare_iiot_2019-2020_runda_3 | Cod sursa (job #1201295) | Cod sursa (job #65029) | Cod sursa (job #537432) | Cod sursa (job #2086293)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define x first
#define y second
using namespace std;
vector<pair<double,double>>sol1;
vector<pair<double,double>>sol2;
pair<double,double> v[120005];
const double EPS = 1e-12;
int n;
void solve_1()
{
sol1.push_back({v[0].x,v[0].y});
sol1.push_back({v[1].x,v[1].y});
for(int i=2;i<n;i++)
{
int m= sol1.size();
while((sol1[m-1].x*v[i].y-sol1[m-1].y*v[i].x)-(sol1[m-2].x*sol1[m-1].y-sol1[m-2].y*sol1[m-1].x)>EPS)
{
m--;
sol1.pop_back();
}
sol1.push_back({v[i].x,v[i].y});
}
}
void solve_2()
{
sol2.push_back({v[n-1].x,v[n-1].y});
sol2.push_back({v[n-2].x,v[n-2].y});
for(int i=n-3;i>=0;i--)
{
int m=sol2.size();
while((sol2[m-1].x*v[i].y-sol2[m-1].y*v[i].x)-(sol2[m-2].x*sol2[m-1].y-sol2[m-2].y*sol2[m-1].x)<EPS&&m>2)
{
m--;
sol2.pop_back();
}
sol2.push_back({v[i].x,v[i].y});
}
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
for(int i=0;i<n;i++)
{
double a,b;
f>>a>>b;
v[i]={a,b};
}
sort(v,v+n);
solve_1();
solve_2();
g<<sol1.size()+sol2.size()-2<<"\n";
for(int i=sol2.size()-2;i>0;i--)
g<<fixed<<sol2[i].x<<" "<<sol2[i].y<<"\n";
for(int i=sol1.size()-1;i>=0;i--)
g<<fixed<<sol1[i].x<<" "<<sol1[i].y<<"\n";
return 0;
}