Pagini recente » Cod sursa (job #2137758) | Cod sursa (job #3326982) | Cod sursa (job #1348876) | Cod sursa (job #2159189) | Cod sursa (job #3352265)
#include<fstream>
#include<algorithm>
#include<iostream>
#include<vector>
#include<iomanip>
#include<stack>
#define inf 1e9+1
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct {
double x, y;
punct() :x(0), y(0) {};
punct(double i, double j) :x(i), y(j) {};
};
//produs determinanti:
// x1 y1 1
// x2 y2 1
// x3 y3 1
//arie => x3*y2+ x2*y1+ x1*y3
// - x3*y1+ x2*y3 + x1*y2
// =>x3(y2-y1)+x2(y1-y3)+ x1(y3-y2)
double calcArieTriunghi(punct a, punct b, punct c) {
return (c.x * (b.y - a.y) + b.x * (a.y - c.y) + a.x * (c.y - b.y)) ;
}
punct start= punct(inf,inf);//in functie de punctul asta vom sorta toate punctele
//trebuie ca punctul asta sa apartina infasuratorii ,deci il luam cel mai din stanga (apoi cel mai de jos) punct
double calcPanta(punct& p1, punct& p2) {
return (p1.y - p2.y) / (p1.x - p2.x);
}
bool cmp(punct a, punct b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
vector<punct> convexHull(vector<punct>& v,int sens) {
sort(v.begin(), v.end(), cmp);//sortam in functie de panta formata cu punctul de incepur
vector<punct>s;//un stack cu punctele de pe infasuratoarea convexa
int stackSize = 0;
for (int i = 0; i < v.size(); ++i) {
while (stackSize >=2 && ((sens==1 && calcArieTriunghi(s[stackSize-2],s[stackSize-1],v[i])>=0)||(sens == -1 && calcArieTriunghi(s[stackSize - 2], s[stackSize - 1], v[i])<=0)))
{
s.pop_back();
stackSize--;
}
s.push_back(v[i]);
stackSize++;
}
return s;
}
int main() {
int n;
fin >> n;
vector<punct>v(n);
int pozFound = 0;
for (int i = 0; i < n; ++i) {
fin >> v[i].x >> v[i].y;
}
vector<punct>upperHalf;
vector<punct>lowerHalf;
upperHalf = convexHull(v, 1);
lowerHalf = convexHull(v, -1);
fout << upperHalf.size() + lowerHalf.size() - 2<< "\n";
for (auto i : upperHalf) {
fout << fixed << setprecision(6) << i.x << " " << i.y << "\n";
}
for (int i = lowerHalf.size() - 2; i >= 1; --i) {
fout << fixed << setprecision(6) << lowerHalf[i].x << " " << lowerHalf[i].y << "\n";
}
return 0;
}