Pagini recente » Cod sursa (job #444798) | Cod sursa (job #1736697) | Cod sursa (job #1684974) | Cod sursa (job #2057175) | Cod sursa (job #2429946)
#include <iostream>
#include <fstream>
#include <queue>
#include <cmath>
#define NMAX 120005
#define inf 2147000000
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int st[NMAX], P, N, k;
double slope[NMAX];
pair<double, double> M[NMAX];
class comp{
public:
bool operator()(int a, int b){
if(slope[a] < slope[b]) return false;
return true;
}
};
priority_queue<int, vector<int>, comp> pq;
void read()
{
double ymin = 1000000001, xmin = 1000000001;
fin >> N;
for(int i = 1; i <= N; i++){
fin >> M[i].first >> M[i].second;
if(M[i].first < xmin)
xmin = M[i].first, ymin = M[i].second, P = i;
else if(M[i].second == xmin && M[i].first < ymin)
ymin = M[i].second, P = i;
}
}
void SlopeSort()
{
double x, y;
for(int i = 1; i <= N; i++){
if(i == P) continue;
x = (M[i].first - M[P].first);
y = (M[i].second - M[P].second);
if(x == 0) slope[i] = inf;
else slope[i] = y/x;
pq.push(i);
}
}
bool convex(){
int x1, x2, x3, y1, y2, y3;
x1 = M[st[k - 2]].first, y1 = M[st[k - 2]].second;
x2 = M[st[k - 1]].first, y2 = M[st[k - 1]].second;
x3 = M[st[k - 0]].first, y3 = M[st[k - 0]].second;
return (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1) > 0;
}
int main()
{
read();
SlopeSort();
k = 2; st[1] = P; st[2] = pq.top(); pq.pop();
while(!pq.empty()){
st[++k] = pq.top(); pq.pop();
while(!convex() && !pq.empty()){
st[--k] = st[k + 1]; pq.pop(); st[k + 1] = 0;
}
}
fout << k << "\n";
for(int i = 1; i <= k; i++) fout << M[st[i]].first << " " << M[st[i]].second << "\n";
return 0;
}