Pagini recente » Cod sursa (job #1626793) | Cod sursa (job #986158) | Cod sursa (job #2123488) | Cod sursa (job #1051235) | Cod sursa (job #417884)
Cod sursa(job #417884)
#include <cstdio>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 1000;
struct Point{
double x, y;
};
Point p[MAX];
int n;
int v[MAX];
int init = 0;
bool pointCmp (int a, int b) {
return (p[a].x - p[init].x) * (p[b].y - p[init].y) < (p[a].y - p[init].y) * (p[b].x - p[init].x);
}
long double sign(Point p1, Point p2, Point p3 ) {
return (long double)p1.x * p2.y + (long double)p2.x * p3.y + p3.x * p1.y - (long double)p1.y * p2.x - (long double)p2.y * p3.x - (long double)p3.y * p1.x;
}
void readPoints()
{
ifstream fin("infasuratoare.in");
fin >> n;
int i;
for (i = 0; i < n; ++i) {
fin >> p[i].x >> p[i].y;
if (p[i].x < p[init].x || (p[i].x == p[init].x && p[i].y < p[init].y)) init = i;
}
fin.close();
}
int main() {
int i, j;
init = 0;
readPoints();
for (i = 0, j = 0; i < n; ++i)
if (i != init)
v[j++] = i;
sort(v, v+n-1, pointCmp);
vector<int> st;
st.push_back(init);
for (i = 0; i < n-1; ++i) {
while (st.size() > 1 && sign(p[st[st.size()-2]], p[st[st.size()-1]], p[v[i]]) > 0)
st.pop_back();
st.push_back(v[i]);
}
reverse(st.begin(), st.end());
FILE * fout = fopen("infasuratoare.out", "w");
fprintf(fout, "%d\n",st.size());
for (i = 0; i < n; ++i)
fprintf(fout, "%.6lf %.6lf\n", p[v[i]].x, p[v[i]].y);
fclose(fout);
return 0;
}