Pagini recente » Cod sursa (job #2340010) | Cod sursa (job #2507099) | Cod sursa (job #1192673) | Cod sursa (job #2426578) | Cod sursa (job #2226162)
#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){
int delta;
int x1=v[x].x; int y1=v[x].y;
int x2=v[y].x; int y2=v[y].y;
int x3=v[z].x; int y3=v[z].y;
delta=(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
if (delta>=0) return 0;
else
return 1;
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
for (int i=0; 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>=0;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;
}