Pagini recente » Cod sursa (job #2870014) | Cod sursa (job #2004661) | Cod sursa (job #1979110) | Cod sursa (job #2070645) | Cod sursa (job #1043223)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
class point{
public:
double x, y;
point(){};
point(double x1, double y1){
x = x1;
y = y1;
}
bool operator ==(point other){
return (x == other.x && y == other.y);
}
};
double dist(point A, point B){
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
double ccw(point A, point B, point C){
return 0.5 * (C.y * (B.x - A.x) + B.y * (A.x - C.x) + A.y * (C.x - B.x)); //C at the left of AB is positive, else negative.
}
vector<point> gv;
point refr;
int n;
int cmp(point x, point y){
if(y == refr)
return 0;
if(x == refr)
return 1;
if(ccw(refr, x, y) == 0){
return dist(refr, y) > dist(refr, x);
}
return (ccw(refr, x, y) >= 0);
}
void pizda_matii(int x, int y){
point aux;
aux = gv[x];
gv[x] = gv[y];
gv[y] = aux;
}
int main(){
ifstream in("infasuratoarea.in");
ofstream out("infasuratoarea.out");
in >> n;
for(int i = 1; i <= n; ++i){
double x, y;
in >> x >> y;
gv.push_back(point(x, y));
}
int compilatorupulii = 0;
for(int i = 1; i < gv.size(); ++i)
if(gv[i].x < gv[compilatorupulii].x)
compilatorupulii = i;
else if(gv[i].y < gv[compilatorupulii].y && gv[i].x == gv[compilatorupulii].x)
compilatorupulii = i;
pizda_matii(0, compilatorupulii);
refr = gv[0];
sort(gv.begin(), gv.end(), cmp);
for(int i = n - 2; i > 0; --i)
if(ccw(gv[i], gv[i + 1], refr) != 0){
for(int j = i + 1, k = n - 1; j < k; ++j, --k)
swap(gv[j], gv[k]);
break;
}
gv.push_back(gv[0]);
vector<int> hull;
int u = 0;
hull.push_back(0);
++u;
for(int i = 1; i <= n; ++i){
hull.push_back(i);
++u;
while(u >= 3)
if(ccw(gv[hull[u - 3]], gv[hull[u - 2]], gv[hull[u - 1]]) < 0){
hull[u - 2] = hull[u - 1];
hull.pop_back();
--u;
}
else
break;
}
hull.pop_back();
--u;
out << u << "\n";
for(int i = 0; i < u; ++i)
out << gv[hull[i]].x << " " << gv[hull[i]].y << "\n";
return 0;
}