Pagini recente » Cod sursa (job #1795972) | Cod sursa (job #1636268) | Cod sursa (job #2271005) | Cod sursa (job #3281585) | Cod sursa (job #937244)
Cod sursa(job #937244)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <algorithm>
using namespace std;
#define maxn 100010
#define inf 10000000000000LL
#define inf2 1000010
#define LL long long
#define LD long double
int N;
int S[maxn], varf;
struct Puncte {
int x, y;
} P[maxn];
struct Pcte {
long double x, y;
} aux1, aux2, aux3;
double HMAX;
LL Produs(Puncte P1, Puncte P2, Puncte P3) {
return (LL)P2.x*P3.y - (LL)P2.x*P1.y - (LL)P1.x*P3.y + (LL)P1.x*P1.y -
(LL)P3.x*P2.y + (LL)P3.x*P1.y + (LL)P1.x*P2.y - (LL)P1.x*P1.y;
}
int cmp(Puncte a, Puncte b) {
if((LL)(a.x-P[1].x)*(b.y-P[1].y) != (LL)(b.x-P[1].x)*(a.y-P[1].y)) {
return (LL)(a.x-P[1].x)*(b.y-P[1].y) > (LL)(b.x-P[1].x)*(a.y-P[1].y);
}
else if(P[1].y==a.y && P[1].y==b.y) {
return (LL)(a.x-P[1].x)*(a.x-P[1].x) + (LL)(a.y-P[1].y)*(a.y-P[1].y) <
(LL)(b.x-P[1].x)*(b.x-P[1].x) + (LL)(b.y-P[1].y)*(b.y-P[1].y);
}
else if(!Produs(a, b, P[1])) {
return a.x < b.x;
}
}
void POP() {
varf--;
}
void PUSH(int a) {
varf++;
S[varf]=a;
}
int main() {
FILE *f1=fopen("rubarba.in", "r"); fstream f2; f2.open("rubarba.out", ios::out);
int i, j, p, q;
int xM = inf, yM = inf;
fscanf(f1, "%d\n", &N);
for(i=1; i<=N; i++) {
fscanf(f1, "%d %d\n", &p, &q);
P[i].x = p; P[i].y = q;
if(P[i].y < yM) { yM = P[i].y; xM = P[i].x; j=i; }
else if(P[i].y == yM && P[i].x < xM) { xM = P[i].x; j=i; }
}
//infasuratoare convexa
swap(P[1], P[j]);
sort(P+2, P+N+1, cmp);
PUSH(1); PUSH(2);
for(i=3; i<=N; i++) {
LL o;
o=Produs(P[S[varf-1]], P[S[varf]], P[i]);
if(o==0) { //punctele is coliniare
PUSH(i);
}
else {
if(o>0) { //intoarcere la stinga - valid
PUSH(i);
}
else { //intoarcere la dreapta - invalid
while(o<0 && varf>1) {
POP();
o=Produs(P[S[varf-1]], P[S[varf]], P[i]);
}
PUSH(i);
}
}
}
int H = varf;
S[varf + 1] = S[1];
HMAX = inf;
for(i=1; i<=H; i++) {
//panta e data de dreapta (S[i], S[i+1]);
long double panta, pantaperp;
long double x, y, x0, y0, x1, y1;
long double y01, y02;
panta = 0;
pantaperp = 0;
x = y = x0 = y0= x1 = y1 = y01 = y02 = 0;
if(P[S[i]].x == P[S[i+1]].x && panta == inf) continue;
else if((LD)(P[S[i+1]].y - P[S[i]].y) / (P[S[i+1]].x - P[S[i]].x) == panta) continue;
if(P[S[i]].x == P[S[i+1]].x) panta = inf;
else panta = (LD)(P[S[i+1]].y - P[S[i]].y) / (P[S[i+1]].x - P[S[i]].x);
//aflu panta perpendicularei
if(P[S[i]].y == P[S[i+1]].y) pantaperp = inf;
else pantaperp = - (LD)(P[S[i+1]].x - P[S[i]].x) / (P[S[i+1]].y - P[S[i]].y);
Puncte susmax = P[S[i]], susmin = P[S[i]];
Puncte stmax = P[S[i]], drmax = P[S[i]];
Pcte cstjos, cstsus, cdrjos;
if(panta == 0 || pantaperp == 0) {
//caut pctele
for(j=1; j<=H; j++) {
if(P[S[j]].y > susmax.y) {
susmax = P[S[j]];
}
if(P[S[j]].y < susmin.y) {
susmin = P[S[j]];
}
}
for(j=1; j<=H; j++) {
if(P[S[j]].x < stmax.x) {
stmax = P[S[j]];
}
if(P[S[j]].x > drmax.x) {
drmax = P[S[j]];
}
}
cstsus.x = stmax.x;
cstsus.y = susmax.y;
cstjos.x = stmax.x;
cstjos.y = susmin.y;
cdrjos.x = drmax.x;
cdrjos.y = susmin.y;
}
else {
x0 = 0;
y01 = susmax.y - panta*(susmax.x - x0);
y02 = susmin.y - panta*(susmin.x - x0);
for(j=1; j<=H; j++) {
//vad unde intersecteaza axa Oy
//aflu susmax
//determin ecuatia dreptei
//verific daca S[j] se afla deasupra
aux3.x = P[S[j]].x; aux3.y = P[S[j]].y;
x1 = 0;
y1 = aux3.y - panta*(aux3.x - x1);
if(y1 - y01 > 0.00000000) {
//se afla deasupra
susmax = P[S[j]];
y01 = susmax.y - panta*(susmax.x - x0);
}
//aflu susmin
//determin ecuatia dreptei
aux3.x = P[S[j]].x; aux3.y = P[S[j]].y;
x1 = 0;
y1 = aux3.y - panta*(aux3.x - x1);
if(y1 - y02 < 0.00000000) {
//se afla dedesubt
susmin = P[S[j]];
y02 = susmin.y - panta*(susmin.x - x0);
}
}
x0 = 0;
y01 = stmax.y - pantaperp*(stmax.x - x0);
y02 = drmax.y - pantaperp*(drmax.x - x0);
for(j=1; j<=H; j++) {
//aflu srmax
//determin ecuatia dreptei
//verific daca S[j] se afla in stinga
aux3.x = P[S[j]].x; aux3.y = P[S[j]].y;
x1 = 0;
y1 = aux3.y - pantaperp*(aux3.x - x1);
if(y1 - y01 < 0.00000000) {
//se afla in stinga
stmax = P[S[j]];
y01 = stmax.y - pantaperp*(stmax.x - x0);
}
//aflu drmax
//determin ecuatia dreptei
aux2.x = x0; aux2.y = y0;
//verific daca S[j] se afla in dreapta
aux3.x = P[S[j]].x; aux3.y = P[S[j]].y;
x1 = 0;
y1 = aux3.y - pantaperp*(aux3.x - x1);
if(y1 - y02 > 0.00000000) {
//se afla in dreapta
drmax = P[S[j]];
y02 = drmax.y - pantaperp*(drmax.x - x0);
}
}
//acum stiu pctele de extrem si pantele dreptelor
//coltul dreapta jos
x0 = susmin.x; y0 = susmin.y;
x1 = drmax.x; y1 = drmax.y;
cdrjos.x = (x0*panta - y0 + y1 - x1*pantaperp) / (panta - pantaperp);
cdrjos.y = y0 + (cdrjos.x - x0)*panta;
//coltul stinga jos
x0 = susmin.x; y0 = susmin.y;
x1 = stmax.x; y1 = stmax.y;
cstjos.x = (x0*panta - y0 + y1 - x1*pantaperp) / (panta - pantaperp);
cstjos.y = y0 + (cstjos.x - x0)*panta;
//coltul stinga sus
x0 = susmax.x; y0 = susmax.y;
x1 = stmax.x; y1 = stmax.y;
cstsus.x = (x0*panta - y0 + y1 - x1*pantaperp) / (panta - pantaperp);
cstsus.y = y0 + (cstsus.x - x0)*panta;
//calculez aria
}
double dist1, dist2;
dist1 = (cdrjos.x - cstjos.x)*(cdrjos.x - cstjos.x) + (cdrjos.y - cstjos.y)*(cdrjos.y - cstjos.y);
dist1 = sqrt(dist1);
dist2 = (LD)(cstsus.x - cstjos.x)*(cstsus.x - cstjos.x) + (LD)(cstsus.y - cstjos.y)*(cstsus.y - cstjos.y);
dist2 = sqrt(dist2);
double rasp;
rasp = (dist1 * dist2);
//cout<<dist1<<" "<<dist2<<" "<<rasp<<endl;
HMAX = min(HMAX, rasp);
}
//fprintf(f2, "%llf", HMAX);
//fprintf(f2, "%lf", HMAX);
f2.setf(ios::fixed,ios::floatfield);
f2.precision(2);
f2<<HMAX<<"\n";
fclose(f1); f2.close();
return 0;
}