Pagini recente » Cod sursa (job #1248573) | Cod sursa (job #2863437) | Cod sursa (job #2130562) | Cod sursa (job #196708) | Cod sursa (job #1879150)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct pct{double x, y;};
pct first;
int n;
double det(pct a, pct b, pct c) {
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cnd(pct a, pct b) {
return det(first, a, b) > 0;
}
int main() {
fin >> n;
vector<pct> P(n+1);
int i, poz = 1;
for (i=1; i<=n; i++)
{
fin >> P[i].x >> P[i].y;
if (P[i].x == P[poz].x)
if (P[i].y < P[poz].y)
poz = i;
if (P[i].x < P[poz].x)
poz = i;
}
P[0] = P[poz];
first = P[0];
swap(P[poz], P[n]);
P.pop_back();
sort(P.begin()+1, P.begin()+n, cnd);
vector<int> S;
S.push_back(0);
S.push_back(1);
for (i=2; i<n; i++)
{
while (S.size() > 1 && det(P[S[S.size()-2]], P[S[S.size()-1]], P[i]) <= 0)
S.pop_back();
S.push_back(i);
}
if (S.size() > 1 && det(P[S[S.size()-2]], P[S[S.size()-1]], P[i]) <= 0)
S.pop_back();
fout << S.size() << '\n';
for (i=0; i<S.size(); i++)
fout << fixed << setprecision(6) << P[S[i]].x << " " << P[S[i]].y << '\n';
return 0;
}