Pagini recente » Cod sursa (job #1170517) | Cod sursa (job #2272071) | Cod sursa (job #3186190) | Cod sursa (job #982123) | Cod sursa (job #2765703)
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int nmax = 12e4;
const int INF = 1 << 30;
int s[nmax + 10]; ///pozitiile punctelor care apartin infasuratoarei convexe.
int n, poz;
struct point{
double x, y, panta;
}v[nmax + 10], origine;
bool cmp(point a, point b){ ///
if(a.panta < b.panta){
return true;
}
else if(a.panta == b.panta && a.x < b.x){
return true;
}
return false;
}
int convex(int i, int k){
point a, b, c;
a = v[s[k - 1]];
b = v[s[k]];
c = v[i];
double S = (a.x - c.x) * (b.y - a.y) + (a.x - b.x) * (a.y - c.y);
if(S > 0){
return 1;
}
return 0;
}
int main(){
cin >> n;
origine.x = origine.y = INF;
for(int i = 1; i <= n; ++i){
cin >> v[i].x >> v[i].y;
if(v[i].x < origine.x || v[i].x == 0 && v[i].y < origine.y){
origine = v[i];
poz = i;
}
}
swap(v[poz], v[1]);
for(int i = 2; i <= n; ++i){
v[i].panta = (v[i].y - origine.y) / (v[i].x - origine.x);
}
sort(v + 2, v + n + 1, cmp);
s[1] = 1, s[2] = 2;
int k = 2;
for(int i = 3; i <= n; ++i){
while(!convex(i, k) && k > 2){
k--;
}
s[++k] = i;
}
cout << k << "\n";
for(int i = 1; i <= k; ++i){
cout << fixed << setprecision(6) << v[s[i]].x << " ";
cout << fixed << setprecision(6) << v[s[i]].y << "\n";
}
return 0;
}