Pagini recente » Cod sursa (job #1607604) | Cod sursa (job #3661) | Cod sursa (job #1393646) | Cod sursa (job #2547938) | Cod sursa (job #679841)
Cod sursa(job #679841)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define NM 120010
#define INF 200000000
#define type double
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct poz{type x,y;} V[NM];
int N,i,IND[NM],ST=0;
bool comp(int a,int b) {
type v1,v2;
v1=(double)(V[a].x-V[ST].x)*(V[b].y-V[ST].y);
v2=(double)(V[b].x-V[ST].x)*(V[a].y-V[ST].y);
return v1<v2;
}
int SK[NM],k=0;
bool right(int a,int b,int c) {
return ((V[a].x*V[b].y+V[a].y*V[c].x+V[b].x*V[c].y-V[b].y*V[c].x-V[a].x*V[c].y-V[a].y*V[b].x)>0);
}
int main () {
f >> N;V[0].x=V[0].y=INF;
for (i=1;i<=N;i++) {
f >> V[i].x >> V[i].y;
if (V[i].x<V[ST].x || (V[i].x==V[ST].x && V[i].y<V[ST].y)) ST=i;
}
for (i=1;i<=N;i++)
if (i!=ST) IND[++IND[0]]=i;
sort(IND+1,IND+IND[0]+1,comp);
SK[++k]=ST;
for (i=1;i<=IND[0];i++) {
if (IND[i]==ST) continue;
while(k>=2 && right(SK[k-1],SK[k],IND[i]))
k--;
SK[++k]=IND[i];
}
g << k << '\n';
g << fixed;
for (i=k;i>=1;i--) g << setprecision(7) << V[SK[i]].x << ' ' << V[SK[i]].y << '\n';
f.close();g.close();
return 0;
}