Pagini recente » Cod sursa (job #1127973) | Cod sursa (job #3256588) | Cod sursa (job #1080396) | Cod sursa (job #430960) | Cod sursa (job #1583572)
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int Nmax = 120005;
int n, nr;
pair <double, double> P[Nmax];
pair <double, double> Sol[Nmax];
double semn(pair<double, double> A, pair<double, double> B, pair<double, double> C)
{
return (A.first*B.second + B.first*C.second + C.first*A.second - A.second*B.first - B.second*C.first - C.second*A.first);
}
bool Crit(pair<double, double> A, pair<double, double> B)
{
return semn(P[1],A,B) > 0;
}
void Read()
{
f>>n;
for(int i = 1; i <=n; i++) f>>P[i].first>>P[i].second;
}
void Solve()
{
int pos = 1;
for(int i = 2; i <= n; i++)
{
if(P[pos].second > P[i].second || (P[pos].second == P[i].second && P[pos].first > P[i].first))
pos = i;
}
swap(P[1], P[pos]);
sort(P+2, P+n+1, Crit);
Sol[1] = P[1]; Sol[2] = P[2]; nr = 2;
for(int i = 3; i <= n; i++)
{
while(nr >= 2 && semn(Sol[nr-1], Sol[nr], P[i]) < 0) nr--;
Sol[++nr] = P[i];
}
}
void Print()
{
g<<nr<<'\n';
for(int i = 1; i <= nr; i++) g<<fixed<<setprecision(9)<<Sol[i].first<<' '<<Sol[i].second<<'\n';
}
int main()
{
Read();
Solve();
Print();
return 0;
}