Pagini recente » Cod sursa (job #379542) | Cod sursa (job #2173268) | Cod sursa (job #1362985) | Cod sursa (job #2498243) | Cod sursa (job #2085675)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 120005
#define x first
#define y second
using namespace std;
pair<double,double> v[NMAX];
vector <pair<double,double>> sol;
int n;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
void solve_1()
{
sol.push_back({v[n-2].x,v[n-2].y});
sol.push_back({v[n-3].x,v[n-3].y});
for(int i=n-4;i>=0;i--)
{
int m=sol.size();
double rez=sol[m-2].x*sol[m-1].y+sol[m-1].x*v[i].y+v[i].x*sol[m-2].y-v[i].x*sol[m-1].y-sol[m-1].x*sol[m-2].y-sol[m-2].x*v[i].y;
while(-rez<0)
{
m--;
sol.pop_back();
rez=sol[m-2].x*sol[m-1].y+sol[m-1].x*v[i].y+v[i].x*sol[m-2].y-v[i].x*sol[m-1].y-sol[m-1].x*sol[m-2].y-sol[m-2].x*v[i].y;
}
sol.push_back({v[i].x,v[i].y});
}
}
void solve_2()
{
sol.push_back({v[0].x,v[0].y});
sol.push_back({v[1].x,v[1].y});
for(int i=2;i<n;i++)
{
int m=sol.size();
double rez=sol[m-2].x*sol[m-1].y+sol[m-1].x*v[i].y+v[i].x*sol[m-2].y-v[i].x*sol[m-1].y-sol[m-1].x*sol[m-2].y-sol[m-2].x*v[i].y;
while(-rez<0)
{
m--;
sol.pop_back();
rez=sol[m-2].x*sol[m-1].y+sol[m-1].x*v[i].y+v[i].x*sol[m-2].y-v[i].x*sol[m-1].y-sol[m-1].x*sol[m-2].y-sol[m-2].x*v[i].y;
}
sol.push_back({v[i].x,v[i].y});
}
}
int main()
{
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();
sol.pop_back();
solve_2();
g<<sol.size()<<"\n";
for(int i=sol.size()-1;i>=0;i--)
g<<fixed<<sol[i].x<<" "<<sol[i].y<<"\n";
return 0;
}