Pagini recente » Cod sursa (job #1886631) | Cod sursa (job #2983530) | Cod sursa (job #983475) | Cod sursa (job #2064951) | Cod sursa (job #1318569)
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
#define INF 9999999
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef long double var;
struct Punct {
var x, y;
Punct(var a, var b) {
x = a; y = b;
}
const bool operator==(const Punct p) const {
return (x == p.x)&&(y == p.y);
}
};
var xmin = INF, ymin = INF;
Punct start(0, 0);
inline var angle(Punct p, Punct q) {
if(p.x == q.x) {
if(p.y < q.y) return -INF;
if(p.y == q.y) return INF+1;
return INF;
}
return (q.y-p.y) / (q.x-p.x);
}
inline bool cmp(const Punct &a, const Punct &b) {
if(a == start) return 1;
if(b == start) return 0;
if(a.x == start.x) return 1;
if(b.x == start.x) return 0;
return (a.y - start.y) * (b.x - start.x) > (a.x - start.x)*(b.y - start.y);
}
vector<Punct> SOL;
vector<Punct> PUNCTE;
int main() {
var x, y;
int n, i;
fin>>n;
for(i=1; i<=n; i++) {
fin>>x>>y;
PUNCTE.push_back(Punct(x, y));
if(x<xmin || x==xmin && y<ymin) {
start = PUNCTE[PUNCTE.size() - 1];
xmin = start.x;
ymin = start.y;
}
}
sort(PUNCTE.begin(), PUNCTE.end(), cmp);
SOL.push_back(PUNCTE[0]);
SOL.push_back(PUNCTE[1]);
int size = 1;
for(i=2; i<n; i++) {
while((SOL[size].x-SOL[size-1].x)*(PUNCTE[i].y-SOL[size].y) > (SOL[size].y - SOL[size-1].y) * (PUNCTE[i].x - SOL[size].x)) {
SOL.pop_back();
size --;
}
SOL.push_back(PUNCTE[i]);
size ++;
}
fout<<size+1<<'\n';
for(int i = size;i>=0; i--) {
fout<<setprecision(30)<<SOL[i].x;
fout<<" ";
fout<<setprecision(30)<<SOL[i].y<<'\n';
}
return 0;
}