Pagini recente » Cod sursa (job #2282929) | Cod sursa (job #736358) | Cod sursa (job #1834209) | Cod sursa (job #1870471) | Cod sursa (job #417881)
Cod sursa(job #417881)
#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;
bool pointCmp (int i, int j) {
return (p[i].x - p[init].x) * (p[j].y - p[init].y) < (p[i].y - p[init].y) * (p[j].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", "r");
fprintf(fout, "%d\n",st.size());
for (i = 0; i < n; ++i)
fprintf(fout, "%.6lf %.6lf\n", p[st[i]].x, p[st[i]].y);
fclose(fout);
//system("pause");
return 0;
}