Pagini recente » Cod sursa (job #760817) | Cod sursa (job #3213225) | Cod sursa (job #696803) | Cod sursa (job #857290) | Cod sursa (job #3280995)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
pair<long double, long double> v[120005];
pair<long double, long double> s[120005];
long double det(const pair<long double, long double> &a, const pair<long double, long double> &b, const pair<long double, long double> &c)
{
return (b.first - a.first)*(c.second - a.second) - (c.first - a.first)*(b.second - a.second);
}
bool cmp(const pair<long double, long double> &a, const pair<long double, long double> &b)
{
return det(v[1], a, b) > 0;
}
int main()
{
in>>n;
for(int i = 1; i<=n; i++)
{
in>>v[i].first>>v[i].second;
}
int poz = 1;
for(int i = 1; i<=n; i++)
{
if(v[i] < v[poz])
{
poz = i;
}
}
swap(v[1], v[poz]);
sort(v + 2, v + n + 1, cmp);
/*for(int i = 1; i<=n; i++)
{
out<<v[i].first<<" "<<v[i].second<<'\n';
}*/
s[1] = v[1];
s[2] = v[2];
int head = 2;
for(int i = 3; i<=n; i++)
{
while(head >= 2 && det(s[head - 1], s[head], v[i]) < 0)
{
head--;
}
head++;
s[head] = v[i];
}
out<<head<<'\n';
for(int i = head; i>=1; i--)
{
out<<setprecision(9)<<fixed<<s[i].first<<" "<<s[i].second<<'\n';
}
return 0;
}