Pagini recente » Cod sursa (job #1504757) | Cod sursa (job #884262) | Rating Neata Maria (marya) | Cod sursa (job #1724088) | Cod sursa (job #942931)
Cod sursa(job #942931)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#define inf 1<<30
#define nmax 120005
#define angle first
#define coord second
using namespace std;
struct point {
double x, y;
};
point temp, source;
vector <pair <double, point> > p;
vector <point> S;
double polar_angle;
point top(vector <point> S) {
return S[S.size()-1];
}
point next_to_top(vector <point> S) {
return S[S.size()-2];
}
int cmp(pair <double, point> a, pair <double, point> b) {
return (a.angle < b.angle);
}
//if the ccw of 3 points is positive, then the segment makes a non-left turn
int ccw(point p1, point p2, point p3) {
return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}
int main() {
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, i, j;
double a, b;
temp.y = 0.0;
f>>n;
for(i=0; i<n; i++) {
f>>a>>b;
temp.x = a;
temp.y = b;
p.push_back(make_pair(0.0, temp));
}
source = p[0].coord;
for(i=1; i<p.size(); i++) {
if(p[i].coord.y < source.y) source = p[i].coord;
else if(p[i].coord.y == source.y && p[i].coord.x < source.x) source = p[i].coord;
}
for(i=0; i<n; i++) {
if(p[i].coord.x == source.x && p[i].coord.y == source.y) polar_angle = -5.0; //it's the source, so it stays first after sorting
else polar_angle = atan2( p[i].coord.y-source.y, p[i].coord.x-source.x );
p[i].angle = polar_angle;
}
sort(p.begin(), p.end(), cmp);
//for(i=0; i<p.size(); i++) g<<p[i].coord.x<<" "<<p[i].coord.y<<": "<<p[i].angle<<"\n";
S.push_back(p[0].coord);
S.push_back(p[1].coord);
S.push_back(p[2].coord);
for(i=3; i<p.size(); i++) {
while( ccw(top(S), next_to_top(S), p[i].coord) > 0 ) S.pop_back();
S.push_back(p[i].coord);
}
g<<S.size()<<"\n";
g<<fixed;
g<<setprecision(12);
for(i=0; i<S.size(); i++) {
g<<S[i].x<<" "<<S[i].y<<"\n";
}
return 0;
}