Pagini recente » Cod sursa (job #1849474) | Clasament FMI No Stress 2012 | Cod sursa (job #3252175) | Cod sursa (job #470294) | Cod sursa (job #2190286)
#include <bits/stdc++.h>
#define DIM 120005
#define x first
#define y second
#define point pair <double,double>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N,pos;
pair <double,double> P[DIM];
point Stack[DIM];
double trig(point p1,point p2,point p3){
return (p2.x-p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y);
}
int cmp(const point &p1,const point &p2){
return trig(P[1],p1,p2) > 0;
}
int main(){
fin >> N;
for(int i=1;i<=N;i++)
fin >> P[i].x >> P[i].y;
pos=1;
for(int i=2;i<=N;i++)
if(P[i].y < P[pos].y || (P[i].y==P[pos].y && P[i].x < P[pos].y))
pos=i;
swap(P[1],P[pos]);
sort(P+2,P+N+1,cmp);
int top=2;
Stack[1]=P[1];
Stack[2]=P[2];
for(int i=3;i<=N;i++){
while(top>=1 && trig(Stack[top-1],Stack[top],P[i]) < 0)
top--;
Stack[++top]=P[i];
}
fout << top << "\n";
for(int i=1;i<=top;i++)
fout << setprecision(6) << fixed << Stack[i].x << " " << setprecision(6) << fixed << Stack[i].y << "\n";
}