Pagini recente » Cod sursa (job #2045493) | Cod sursa (job #952287) | Clasament copacabana | Cod sursa (job #2324771) | Cod sursa (job #2226165)
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int afis[140000];
int n;
struct vct{
double x,y;};
vct v[140000];
bool cmp(vct A, vct B){
if (A.y==B.y)
return A.x<B.x;
else
return A.y<B.y;
}
int intoarcere(int x, int y, int z){
double delta,a1,a2,a3,b1,b2,b3;
a1=v[x].x; b1=v[x].y;
a2=v[y].x; b2=v[y].y;
a3=v[z].x; b3=v[z].y;
delta=a1*b2+a2*b3+a3*b1-a3*b2-a1*b3-a2*b1;
if(delta>=0)
return 1;
else
return 0;
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
for (int i=1; i<=n;i++){
f>>v[i].x>>v[i].y;
}
sort(v+1, v+1+n, cmp);
afis[1]=1;
afis[2]=2;
int t=2;
for(int i=3; i<=n;i++){
if (intoarcere(afis[t-1],afis[t],i)==0){afis[++t]=i;}
else{
while(intoarcere(afis[t-1],afis[t],i)==1&&t>=2)
t--;
afis[++t]=i;
}
}
afis[++t]=n-1;
for(int i=n-2; i>=1;i--){
if (intoarcere(afis[t-1],afis[t],i)==0){afis[++t]=i;}
else{
while(intoarcere(afis[t-1],afis[t],i)==1&&t>=2)
t--;
afis[++t]=i;
}
}
g<<t-1<<'\n';
for(int i=1;i<t;i++)
g<<fixed<<setprecision(6)<<v[afis[i]].x<<' '<<fixed<<setprecision(6)<<v[afis[i]].y<<'\n';
return 0;
}