Pagini recente » Cod sursa (job #2266780) | Cod sursa (job #453939) | Cod sursa (job #2848092) | Cod sursa (job #1490478) | Cod sursa (job #1614066)
#include <fstream>
#include <vector>
#include <algorithm>
#define f first
#define s second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int S[120050], n, i, k;
vector<pair<double, double> > points(120050);
vector<int> infConvex;
double sarrus(int x, int y, int z) {
double yur, prk;
yur = (points[x].f * points[y].s + points[y].f * points[z].s + points[z].f * points[x].s);
prk = (points[x].f * points[z].s + points[y].f * points[x].s + points[z].f * points[y].s);
return yur - prk;
}
int main()
{
fin>>n;
for (i = 0 ; i < n ; i++) {
fin>>points[i].f>>points[i].s;
}
sort(points.begin() , points.begin() + n);
k = -1;
for (i = 0 ; i < n ; i++) {
while (k >= 1 && sarrus(S[ k - 1 ], S[ k ], i) > 0)
k--;
S[ ++k ] = i;
}
for (i = 0 ; i <= k ; i++) {
infConvex.push_back(S[i]);
}
k = -1;
for (i = n - 1 ; i >= 0 ; i--) {
while (k >= 1 && sarrus(S[ k - 1 ], S[ k ], i) > 0)
k--;
S[ ++k ] = i;
}
for (i = 1 ; i < k ; i++) {
infConvex.push_back(S[i]);
}
fout<<infConvex.size();
fout<<setprecision(6)<<fixed;
for (i = infConvex.size() - 1 ; i >= 0 ; i--)
fout<<'\n'<<points[infConvex[i]].f<<' '<<points[infConvex[i]].s;
return 0;
}