Pagini recente » Cod sursa (job #1321989) | Cod sursa (job #2467094) | Cod sursa (job #2815527) | Cod sursa (job #2689903) | Cod sursa (job #391022)
Cod sursa(job #391022)
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
#define INF 1000000000
int N, varf;
struct Puncte {
double x;
double y;
} P[120002], S[120002], aux;
int cmp(Puncte a, Puncte b) {
return (double)(a.x-P[1].x)*(b.y-P[1].y) > (double)(b.x-P[1].x)*(a.y-P[1].y);
}
double Produs(Puncte P1, Puncte P2, Puncte P3) {
return (double)P2.x*P3.y - P2.x*P1.y - P1.x*P3.y + P1.x*P1.y -
P3.x*P2.y + P3.x*P1.y + P1.x*P2.y - P1.x*P1.y;
}
void POP() {
varf--;
}
void PUSH(Puncte a) {
varf++;
S[varf]=a;
}
int main() {
FILE *f1=fopen("infasuratoare.in", "r"), *f2=fopen("infasuratoare.out", "w");
int i, j, p, q;
double xmin=INF, ymin=INF;
fscanf(f1, "%d", &N);
for(i=1; i<=N; i++) {
fscanf(f1, "%lf%lf", &P[i].x, &P[i].y);
if(P[i].y<ymin) {
xmin=P[i].x;
ymin=P[i].y;
p=i;
}
else if(P[i].y==ymin && P[i].x<xmin) {
xmin=P[i].x;
p=i;
}
}
aux=P[1]; P[1]=P[p]; P[p]=aux;
sort(P+2, P+N+1, cmp);
PUSH(P[1]); PUSH(P[2]);
for(i=3; i<=N; i++) {
//S[varf-1], S[varf], P[i]
double o=Produs(S[varf-1], S[varf], P[i]);
if(o==0) {
//cele 3 pcte is coliniare
POP();
PUSH(P[i]);
}
else if(o>0) {
//avem intoarcere la stinga (valida)
PUSH(P[i]);
}
else if(o<0) {
//avem intoarcere la dreapta
while(varf>1 && o<=0) {
POP();
o=Produs(S[varf-1], S[varf], P[i]);
}
PUSH(P[i]);
}
}
fprintf(f2, "%d\n", varf);
for(i=1; i<=varf; i++) {
fprintf(f2, "%lf %lf\n", S[i].x, S[i].y);
}
fclose(f1); fclose(f2);
return 0;
}