Pagini recente » Cod sursa (job #795879) | Monitorul de evaluare | Cod sursa (job #543653) | Cod sursa (job #1040074) | Cod sursa (job #2087466)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#define x first
#define y second
using namespace std;
const double EPS = 1e-12;
pair<double,double>v[120005];
vector<pair<double,double>>sol1;
vector<pair<double,double>>sol2;
int n;
double det(pair<double,double>a,pair<double,double>b,pair<double,double>c)
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
void solve()
{
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(double p=det(sol1[m-2],sol1[m-1],v[i])>EPS &&m>1)
{
m--;
sol1.pop_back();
}
sol1.push_back({v[i].x,v[i].y});
}
sol2.push_back({v[0].x,v[0].y});
sol2.push_back({v[1].x,v[1].y});
int d=sol2.size();
for(int i=2;i<n;i++)
{
int m=sol2.size();
while(double p=det(sol2[m-2],sol2[m-1],v[i])<EPS&&p>-EPS &&m>d)
{
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);
for(int i=0;i<n;i++)
cout<<v[i].x<<" "<<v[i].y<<"\n";
cout<<endl;
solve();
g<<sol1.size()+sol2.size()-3<<"\n";
g<<fixed;
for(int i=2;i<sol2.size();i++)
g<<sol2[i].x<<" "<<sol2[i].y<<"\n";
for(int i=sol1.size()-2;i>=0;i--)
g<<sol1[i].x<<" "<<sol1[i].y<<"\n";
return 0;
}