Pagini recente » Cod sursa (job #1930781) | Cod sursa (job #1120957) | Cod sursa (job #462633) | Cod sursa (job #2250650) | Cod sursa (job #2095177)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair <long double, long double> v[120001];
vector<pair <long double, long double>> sol;
long double determinant (long double x_1, long double y_1, long double x_2, long double y_2, long double x_3, long double y_3 )
{
return x_1*y_2+x_2*y_3+x_3*y_1-y_1*x_2-y_2*x_3-y_3*x_1;
}
bool cmp ( const pair <long double, long double> a, const pair <long double, long double> b)
{
if ( determinant(v[0].first, v[0].second, a.first, a.second, b.first, b.second) < 0) return false;
if (determinant(v[0].first, v[0].second, a.first, a.second, b.first, b.second) == 0 ) return 0;
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n;
fin>>n;
fin>>v[0].first>>v[0].second;
for ( int i = 1; i < n; ++i )
fin>>v[i].first>>v[i].second;
sort (v+1, v+n, cmp );
v[n] = v[0];
sol.push_back(v[0]);
for ( int i = 1; i < n; ++i )
{
bool prost = true;
while ( sol.size() >= 2 && prost )
{
prost = false;
pair < long double, long double > a = sol.back();
sol.pop_back();
if ( determinant(sol.back().first, sol.back().second, a.first, a.second, v[i].first, v[i].second) <= 0 ) prost = true;
else sol.push_back(a);
}
sol.push_back(v[i]);
}
fout<<sol.size()<<'\n';
for ( int i = 0; i < sol.size(); ++i )
fout<<fixed<<setprecision(6)<<sol[i].first<<" "<<sol[i].second<<'\n';
}