Pagini recente » Cod sursa (job #3132539) | Cod sursa (job #2540996) | Cod sursa (job #512479) | Cod sursa (job #193256) | Cod sursa (job #2556981)
/**
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){
double nr = (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
return (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
}
bool cmp(Punct p0, Punct p1){
return orientare(P0, p0, p1)<0;
}
void punctMinim(){
int poz=1;
for(int i = 2; i<=n; i++)
if(P[i].y<P[poz].y)
poz = i;
else if(P[i].y == P[poz].y && P[i].x<P[poz].x)
poz = i;
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-2], S[nr-1], 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=0; i<nr; i++)
g<<setprecision(9)<<S[i].x<<" "<<S[i].y<<'\n';
}
int main()
{
citire();
punctMinim();
construiesc_infas();
afisare();
return 0;
}