Pagini recente » Borderou de evaluare (job #1523032) | Borderou de evaluare (job #3034673) | Borderou de evaluare (job #1474670) | Borderou de evaluare (job #2590760) | Cod sursa (job #3300653)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct Punct {
double x,y;
bool operator<(const Punct& alt) const {
return x<alt.x || (x==alt.x && y<alt.y);
}
bool operator==(const Punct&alt)const {
return x==alt.x && y==alt.y;
}
};
double orientare(const Punct& a, const Punct& b, const Punct& c) {
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,i,k;
fin>>n;
vector<Punct> puncte(n);
for(i=0;i<n;i++)
fin>>puncte[i].x>>puncte[i].y;
sort(puncte.begin(),puncte.end());
vector<Punct> infasuratoare;
for(i=0;i<n;i++) {
while(infasuratoare.size()>=2 && orientare(infasuratoare[infasuratoare.size()-2],infasuratoare[infasuratoare.size()-1],puncte[i])<=0)
infasuratoare.pop_back();
infasuratoare.push_back(puncte[i]);
}
k=infasuratoare.size();
for(i=n-2;i>=0;i--) {
while(infasuratoare.size()>k && orientare(infasuratoare[infasuratoare.size()-2],infasuratoare[infasuratoare.size()-1],puncte[i])<=0)
infasuratoare.pop_back();
infasuratoare.push_back(puncte[i]);
}
if (infasuratoare.size()>1 && infasuratoare.front()==infasuratoare.back())
infasuratoare.pop_back();
if (infasuratoare.size() > 1 && infasuratoare.front() == infasuratoare.back())
infasuratoare.pop_back();
fout<<infasuratoare.size()<<"\n";
fout <<fixed <<setprecision(6);
for (i=0;i<infasuratoare.size();i++) {
fout << infasuratoare[i].x <<" "<< infasuratoare[i].y<<"\n";
}
return 0;
}