Pagini recente » Cod sursa (job #861368) | Cod sursa (job #3174585) | Cod sursa (job #2788625) | Cod sursa (job #1644916) | Cod sursa (job #2842497)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
#define cx first
#define cy second
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
pair <double, double> pct[120005];
vector <int> sus, jos, ans; /// suspisisus
double arie(int a, int b, int c)
{
/// ax ay 1 )
/// bx by 1 ) => d = ax * by + ay * cx + bx * cy - by * cx - ay * bx - ax * cy
/// cx cy 1 )
return pct[a].cx * pct[b].cy + pct[a].cy * pct[c].cx + pct[b].cx * pct[c].cy - pct[b].cy * pct[c].cx - pct[a].cy * pct[b].cx - pct[a].cx * pct[c].cy;
}
int cadran(int x)
{
if(pct[x].cx >= 0 && pct[x].cy >= 0)
return 1;
if(pct[x].cx < 0 && pct[x].cy >= 0)
return 2;
if(pct[x].cx < 0 && pct[x].cy < 0)
return 3;
if(pct[x].cx >= 0 && pct[x].cy < 0)
return 4;
}
bool cmp(int a, int b)
{
if(cadran(a) == cadran(b))
return (pct[a].cy / pct[a].cx) < (pct[b].cy / pct[b].cx);
return cadran(a) < cadran(b);
}
int main()
{
fin >> n;
for(int i = 1; i <= n; i++)
fin >> pct[i].cx >> pct[i].cy;
sort(pct + 1, pct + n + 1);
sus.push_back(1);
jos.push_back(1);
for(int i = 2; i < n; i++)
{
if(arie(sus.back(), i, n) > 0)
sus.push_back(i);
if(arie(jos.back(), i, n) < 0)
jos.push_back(i);
}
sus.push_back(n);
jos.push_back(n);
fout << sus.size() + jos.size() - 2 << '\n';
for(int ind : sus)
ans.push_back(ind);
for(int ind : jos)
{
if(ind != 1 && ind != n)
ans.push_back(ind);
}
sort(ans.begin(), ans.end(), cmp);
fout << setprecision(12) << fixed;
for(int ind : ans)
fout << pct[ind].cx << ' ' << pct[ind].cy << '\n';
return 0;
}