Pagini recente » Cod sursa (job #2679800) | Cod sursa (job #1567535) | Cod sursa (job #1119990) | Cod sursa (job #2144717) | Cod sursa (job #2887116)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <iomanip>
#include <algorithm>
using namespace std;
const string filename = "infasuratoare";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
const int maxN = 120005;
int n;
struct point {
double cx, cy;
bool operator < (const point &other) const
{
if(cx == other.cx)
return cy < other.cy;
return cx < other.cx;
}
}pct[maxN];
vector <int> sus, jos, ans;
double arie(int a, int b, int c)
{
/// ax ay 1 )
/// bx by 1 ) => A = ax * by + bx * cy + cx * ay - ax * cy - bx * ay - cx * by
/// 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 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++)
{
while(sus.size() > 1 && arie(sus[sus.size() - 2], sus[sus.size() - 1], i) > 0)
sus.pop_back();
sus.push_back(i);
while(jos.size() > 1 && arie(jos[jos.size() - 2], jos[jos.size() - 1], i) < 0)
jos.pop_back();
jos.push_back(i);
}
ans = jos;
reverse(sus.begin(), sus.end());
for(int ind : sus)
if(ind != 1 && ind != n)
ans.push_back(ind);
fout << ans.size() << '\n';
fout << setprecision(12) << fixed;
for(int ind : ans)
fout << pct[ind].cx << ' ' << pct[ind].cy << '\n';
return 0;
}