Pagini recente » Cod sursa (job #172446) | Cod sursa (job #194774) | Cod sursa (job #494705) | Cod sursa (job #1659879) | Cod sursa (job #2044397)
#include <bits/stdc++.h>
#define nmax 120003
using namespace std;
struct punct{
double x, y;
};
punct a[nmax];
int n;
int st[nmax], top;
bool v[nmax];
double F(int i, int j, int p){
/// <0 daca a[p] este in semiplanul -
/// al dreptei [a[i],a[j]]
return a[p].x * (a[i].y - a[j].y) + a[p].y * (a[j].x - a[i].x) + a[i].x * a[j].y - a[j].x * a[i].y;
}
void Citire(){
int i;
ifstream f("infasuratoare.in");
f >> n;
for(i = 1; i <= n; i++)
f>>a[i].x>>a[i].y;
f.close();
}
inline bool Compare(punct A, punct B){
if(A.y == B.y)
return A.x < B.x;
return A.y < B.y;
}
///Hill's algorithm
void Hill(){
int i;
sort(a+1, a+n+1, Compare);
st[++top] = 1;
st[++top] = 2;
//v[1] = v[2] = true;
v[2] = true;
for(i=3; i<=n; i++) {
while(top>1 && F(st[top-1], st[top], i)<0) {
v[top] = false;
top--;
}
st[++top] = i;
v[i] = true;
}
for(i=n-1; i>=1; i--){
if(!v[i]){
while(F(st[top-1], st[top], i)<0) {
v[top] = false;
top--;
}
st[++top] = i;
v[i] = true;
}
}
}
void Afisare(){
int i;
ofstream g("infasuratoare.out");
g << top-1 << '\n';
for(i = 1; i<top; i++)
g << setprecision(12) << fixed << a[st[i]].x << ' ' << a[st[i]].y << '\n';
}
int main(){
Citire();
Hill();
Afisare();
return 0;
}