Pagini recente » Cod sursa (job #223958) | Cod sursa (job #2203010) | Cod sursa (job #2628556) | Cod sursa (job #1227753) | Cod sursa (job #3246410)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define pff pair<float, float>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int NMAX = 120000 + 1;
int n;
bool cmp_cresc(const pff& a, const pff& b)
{
if(a.first < b.first)
{
return 1;
}
if(a.first == b.first)
{
return a.second < b.second;
}
if(a.first > b.first)
{
return 0;
}
return 0;
}
float arie(pff A, pff B, pff C)
{
return (A.first * B.second + B.first * C.second + C.first * A.second)
-(C.first * B.second + A.first * C.second + B.first * A.second);
}
int semn(pff A, pff B, pff C)
{
float area = arie(A, B, C);
if(area > 0) //sus sau stanga
{
return 1;
}
if(area < 0) //jos sau dreapta
{
return -1;
}
return 0; //apartine AB
}
//void afis_vector(vector<pff> sir)
//{
// int marime = sir.size();
// for(int i=marime-1; i>=0; i--)
// {
// out<<fixed<<setprecision(6)<<sir[i].first<<" "<<sir[i].second<<"\n";
// }
// out<<"\n";
//}
int main()
{
in>>n;
vector<pff> v;
for(int i=1; i<=n; i++)
{
float x,y;
in>>x>>y;
v.push_back(make_pair(x, y));
}
sort(v.begin(), v.end(), cmp_cresc);
//afis_vector(v);
pff left_limit = v[0];
pff right_limit = v[n-1];
vector<int> stiva;
stiva.push_back(0);
for(int i=1; i<n; i++)
{
if(semn(left_limit, right_limit, v[i]) == -1)
{
while(stiva.size() >= 2 && semn(v[stiva[stiva.size()-2]], v[stiva.back()], v[i]) == -1)
{
stiva.pop_back();
}
stiva.push_back(i);
}
}
int marime = stiva.size();
stiva.push_back(n-1);
for(int i=n-2; i>=0; i--)
{
if(semn(left_limit, right_limit, v[i]) == 1)
{
while(stiva.size() > marime && semn(v[stiva[stiva.size()-2]], v[stiva.back()], v[i]) == -1)
{
stiva.pop_back();
}
stiva.push_back(i);
}
}
marime = stiva.size();
out<<marime<<"\n";
for(int i=0; i<marime; i++)
{
out<<v[stiva[i]].first<<" "<<v[stiva[i]].second<<"\n";
}
return 0;
}