Pagini recente » Cod sursa (job #978240) | Cod sursa (job #2848308) | Cod sursa (job #45750) | Cod sursa (job #842572) | Cod sursa (job #2682245)
#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int N = 120000;
struct punct{
double x, y;
} coords[N];
bool cmp(punct a, punct b){
if(a.y < b.y)
return true;
if(a.y == b.y && a.x < b.x)
return true;
return false;
}
double getArea(punct p1, punct p2, punct p3){
double area = p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
return area;
}
vector <punct> stiva1;
vector <punct> stiva2;
int main()
{
int n, i, top1, top2;
double area;
fin >> n;
for(i = 0; i < n; i++)
fin >> coords[i].x >> coords[i].y;
sort(coords, coords + n, cmp);
stiva1.push_back(coords[0]);
stiva2.push_back(coords[0]);
for(i = 1; i < n; i++){
area = getArea(coords[0], coords[n - 1], coords[i]);
if(area >= 0){
top1 = (int)stiva1.size();
while(top1 > 1 && getArea(stiva1[top1 - 2], stiva1[top1 - 1], coords[i]) >= 0){
stiva1.pop_back();
top1--;
}
stiva1.push_back(coords[i]);
}
if(area <= 0){
top2 = (int)stiva2.size();
while(top2 > 1 && getArea(stiva2[top2 - 2], stiva2[top2 - 1], coords[i]) <= 0){
stiva2.pop_back();
top2--;
}
stiva2.push_back(coords[i]);
}
}
top1 = (int)stiva1.size();
top2 = (int)stiva2.size();
fout << top1 + top2 - 2 << "\n";
fout << setprecision(6) << fixed;
for(i = 0; i < top2; i++)
fout << stiva2[i].x << " " << stiva2[i].y << "\n";
for(i = top1 - 2; i > 0; i--)
fout << stiva1[i].x << " " << stiva1[i].y << "\n";
return 0;
}