Pagini recente » Cod sursa (job #105042) | Cod sursa (job #1933085) | Cod sursa (job #1392453) | Cod sursa (job #1940624) | Cod sursa (job #1773187)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct Point {
double x, y;
};
int n;
vector<Point> a, h;
double det(Point a, Point b, Point c) {
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
bool comparePoints(Point a, Point b) {
return a.y<b.y || a.y==b.y && a.x<b.x;
}
bool compareAngles(Point x, Point y) {
return det(a[0], x, y)>0;
}
void readData() {
ifstream cin("infasuratoare.in");
cin>>n;
a.resize(n);
for (int i = 0; i<n; i++) {
cin>>a[i].x>>a[i].y;
}
}
void sortPoints() {
int p = min_element(a.begin(), a.end(), comparePoints) - a.begin();
swap(a[0], a[p]);
sort(a.begin()+1, a.end(), compareAngles);
}
void convexHull() {
h.push_back(a[0]);
h.push_back(a[1]);
for (int i = 2; i < a.size(); i++) {
while (h.size()>1 && det(h[h.size()-2], h[h.size()-1], a[i])<=0) {
h.erase(h.end()-1);
}
h.push_back(a[i]);
}
}
void writeData() {
ofstream cout("infasuratoare.out");
cout<<h.size()<<"\n";
for (int i = 0; i < h.size(); i++) {
cout<<h[i].x<<" "<<h[i].y<<"\n";
}
}
int main() {
readData();
sortPoints();
convexHull();
writeData();
return 0;
}