Pagini recente » Cod sursa (job #3292065) | Cod sursa (job #3292729) | Cod sursa (job #3284994) | Clasamentul arhivei educationale | Cod sursa (job #3292682)
#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct pct {
int x,y;
} v[MAX];
int stiva[MAX];
long long cross(const pct &a,const pct &b,const pct &c) {
return (long long)(b.x-a.x)*(c.y-a.y)-(long long)(b.y-a.y)*(c.x-a.x);
}
bool cmp(const pct &a,const pct &b) {
long long c=cross(v[1],a,b);
if(c==0) {
long long da=(long long)(a.x-v[1].x)*(a.x-v[1].x)+(a.y-v[1].y)*(a.y-v[1].y);
long long db=(long long)(b.x-v[1].x)*(b.x-v[1].x)+(b.y-v[1].y)*(b.y-v[1].y);
return da<db;
}
return c>0;
}
int main()
{
int n;
in >> n;
for (int i=1; i<=n; i++) {
in >> v[i].x >> v[i].y;
}
int pi=1;
///gasim punctul cu y minim (si, in caz de egalitate, cu x minim)
for(int i=2; i<=n; i++) {
if(v[i].y<v[pi].y||(v[i].y==v[pi].y && v[i].x<v[pi].x)){
pi=i;
}
}
swap(v[1],v[pi]);
sort(v+2,v+n+1,cmp);
stiva[1]=1;
stiva[2]=2;
int cnt=2;
for (int i=3; i<=n; i++) {
while(cnt>=2 && cross(v[stiva[cnt-1]],v[stiva[cnt]],v[i])<=0){
cnt--;
}
stiva[++cnt]=i;
}
int start=1;
out << cnt << '\n';
for (int i=0; i<cnt; i++) {
int idx=stiva[(start+i-1)%cnt+1];
out << v[idx].x << " " << v[idx].y << '\n';
}
return 0;
}