Pagini recente » Cod sursa (job #481019) | Cod sursa (job #2738367) | Cod sursa (job #359744) | Cod sursa (job #2349991) | Cod sursa (job #2983548)
#include<bits/stdc++.h>
using namespace std;
//ifstream f("file.in");
//ifstream f("p2sah.in");
//ofstream g("p2sah.out");
struct Point {
float x, y;
int crossZ(Point p) {
return x*p.y - y*p.x;
}
bool notEqual(Point p) {
return x != p.x || y != p.y;
}
};
bool verif[120000];
vector<Point> readPoints(char* path) {
ifstream f(path);
int n;
f>>n;
vector<Point> points(n);
for(int i=0; i<n; i++) {
f >> points[i].x >> points[i].y;
}
return points;
}
Point minimX(vector<Point>& points) {
Point minP = points[0];
for(int i=1; i<points.size(); i++) {
if(minP.x > points[i].x)
minP = points[i];
}
return minP;
}
bool allCrossIsPositive(Point u, Point p, vector<Point> &points) {
for(int i=0; i<points.size(); i++) {
Point v = {points[i].x - p.x, points[i].y - p.y};
if(points[i].notEqual(p)) {
if(u.crossZ(v) < 0)
return false;
}
}
return true;
}
Point nextPointOnPoly(vector<Point> &points, Point p) {
for(int i=0; i<points.size(); i++) {
Point u = {points[i].x- p.x, points[i].y - p.y};
if(points[i].notEqual(p) && !verif[i]) {
if(allCrossIsPositive(u, p, points)) {
verif[i] = true;
return points[i];
}
}
}
cout << "aici nu trebuia sa se ajunga";
exit(-1);
}
vector<Point> findPolygon(vector<Point>& points) {
vector<Point> poly;
Point minP = minimX(points);
Point p = minP;
do {
p = nextPointOnPoly(points, p);
poly.push_back(p);
} while(p.notEqual(minP));
return poly;
}
int main(){
vector<Point> points = readPoints("infasuratoare.in");
vector<Point> result = findPolygon(points);
ofstream g("infasuratoare.out");
g<<result.size()<<'\n';
for(Point p : result) {
g << fixed << setprecision(6) << p.x<<" "<< p.y <<'\n';
}
return 0;
}