Pagini recente » Cod sursa (job #2265578) | Cod sursa (job #364671) | Cod sursa (job #1023016) | Cod sursa (job #2689165) | Cod sursa (job #2557207)
/**
Fara puncte coliniare
**/
#define NMAX 120005
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct{
double x, y;
}P[NMAX], P0;
Punct S[NMAX];
int n, nr=0;
double orientare(Punct A, Punct B, Punct C){
return (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
}
bool cmp(Punct B, Punct C){
return (orientare(P0, B, C)<0);
}
void punctMinim(){
int poz=1;
for(int i = 2; i<=n; i++)
if(P[i].x<P[poz].x)
poz = i;
else if(P[i].x == P[poz].x && P[i].y < P[poz].y)
poz = i;
P0=P[poz];
swap(P[1], P[poz]); /// imi aduc pe prima pozitie elementul minim
sort(P+2, P+n+1, cmp);
}
void construiesc_infas(){
S[++nr]=P[1];
S[++nr]=P[2];
for(int i=3; i<=n; i++){
while(nr>=2 && orientare(S[nr-1], S[nr], P[i])>0)
nr--;
S[++nr] = P[i];
}
}
void citire(){
f>>n;
for(int i=1; i<=n; i++){
f>>P[i].x>>P[i].y;
}
}
void afisare(){
g<<fixed;
g<<nr<<'\n';
for(int i=nr; i>=1; i--)
g<<setprecision(9)<<S[i].x<<" "<<S[i].y<<'\n';
}
int main()
{
citire();
punctMinim();
construiesc_infas();
afisare();
return 0;
}