Pagini recente » Cod sursa (job #1134000) | Cod sursa (job #3220261) | Cod sursa (job #1677770) | Cod sursa (job #857767) | Cod sursa (job #1647301)
#include <cstdio>
#include <algorithm>
#define NMAX 120010
using namespace std;
struct pct{
double x, y;
};
pct P[NMAX], S[NMAX];
int vfS, n;
void citire();
void Graham();
inline bool cmp (const pct&, const pct&);
inline double prodi (const pct&, const pct&, const pct&);
void afisare();
int main(){
citire();
Graham();
afisare();
return 0;
}
void citire(){
int i;
FILE*fin=fopen ("infasuratoare.in", "r");
fscanf(fin, "%d", &n);
for (i=1; i<=n; ++i)
fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);
fclose(fin);
return;
}
void Graham(){
pct xy=P[1];
int vfmin=1, i;
for (i=2; i<=n; ++i)
if (P[i].y<xy.y || (P[i].y==xy.y && P[i].x<xy.x)){
xy=P[i];
vfmin=i;
}
swap (P[vfmin], P[1]);
sort (P+2, P+n+1, cmp);
S[1]=P[1]; S[2]=P[2]; vfS=2;
for (i=3; i<=n; ++i){
while (vfS>1 && prodi(S[vfS-1], S[vfS], P[i])<=0)
--vfS;
S[++vfS]=P[i];
}
return;
}
inline double prodi (const pct &a, const pct &b, const pct &c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
//a-b-c
//returneaza o valoare pozitiva daca in b se face o intoarcere la stanga
//val negativa altfel
}
inline bool cmp (const pct &a, const pct &b){
return prodi(P[1], a, b)>0;
}
void afisare(){
FILE*fout=fopen ("infasuratoare.out", "w");
int i;
fprintf(fout, "%d\n", vfS);
for (i=1; i<=vfS; ++i)
fprintf(fout, "%f %f\n", S[i].x, S[i].y);
fclose(fout);
return;
}