Pagini recente » Cod sursa (job #1869823) | Cod sursa (job #431500) | Monitorul de evaluare | Cod sursa (job #2688386) | Cod sursa (job #2961509)
#include <iomanip>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#define MAXN 100000
#define MAXVAL 1000000
#define DEBUG 0
using namespace std;
struct Point{
double x;
double y;
int id;
};
struct Edge{
double a;
double b;
};
struct SortEdge{
double upper;
double lower;
bool minus;
Point end;
};
Point getIntersection(Edge e1, Edge e2){
Point r;
r.x = (e2.b - e1.b) / (e1.a - e2.a);
r.y = e1.a * r.x + e1.b;
return r;
}
Point getProjection(Point p, Edge e){
Edge pp;
pp.a = -1 / e.a;
pp.b = p.y - pp.a * p.x;
//printf(" --- %.2f %.2f --- \n", pp.a, pp.b);
return getIntersection(e, pp);
}
Edge getEdge(Point p1, Point p2){
Edge r;
if(p1.x == p2.x){
r.a = MAXVAL;
r.b = p1.x;
return r;
}
r.a = (p1.y - p2.y) / (p1.x - p2.x);
r.b = p1.y - r.a * p1.x;
return r;
}
double getDistance(Point p1, Point p2){
long double difx = p1.x - p2.x;
long double dify = p1.y - p2.y;
return sqrt(difx * difx + dify * dify);
}
// Returneaza true daca a trebuie pus inainte de b
bool sortCompare(SortEdge a, SortEdge b){
if(a.minus && !b.minus)
return true;
if(!a.minus && b.minus)
return false;
double left = a.upper * b.lower;
double right = a.lower * b.upper;
if(a.minus && b.minus)
return left > right;
return left < right;;
}
/*
1 - trigonometric
0 - colineare
-1 - clockwise
*/
int getOrder(Point a, Point b, Point c){
int left = (a.y - b.y) * (b.x - c.x);
int right = (b.y - c.y) * (a.x - b.x);
if(left > right)
return 1;
if(right == left)
return 0;
return -1;
}
Point p[MAXN], r[MAXN], u[MAXN];
SortEdge v[MAXN];
int main(){
int n, i, j, dr, mini;
double min, minx, maxx, miny, maxy, maxd, dist;
ifstream fin ("rubarba.in");
fin >> n;
min = MAXVAL;
miny = MAXVAL;
minx = MAXVAL;
minx = -MAXVAL;
maxx = -MAXVAL;
for(i = 0; i < n; i ++){
fin >> p[i].x >> p[i].y;
p[i].id = i + 1;
if(p[i].y < min){
min = p[i].y;
mini = i;
}
if(p[i].y < miny)
miny = p[i].y;
if(p[i].y > maxy)
maxy = p[i].y;
if(p[i].x < minx)
minx = p[i].x;
if(p[i].x > maxx)
maxx = p[i].x;
}
fin.close();
// Punem punctul de y minim la pozitia p[0]
Point aux = p[mini];
p[mini] = p[0];
p[0] = aux;
// Ordonam punctele in ordinea pantei dreptei
for(i = 1; i < n; i ++){
v[i - 1].end = p[i];
v[i - 1].upper = p[i].y - p[0].y;
v[i - 1].lower = p[i].x - p[0].x;
if(v[i - 1].lower < 0){
v[i - 1].lower = - v[i - 1].lower;
v[i - 1].minus = true;
}
}
sort(v, v + n - 1, sortCompare);
if(DEBUG){
for(i = 0; i < n - 1; i++){
printf("%d: ", v[i].end.id);
if(v[i].minus)
printf("- ");
else
printf(" ");
printf("%.1f %.1f\n", v[i].upper, v[i].lower);
}
printf("\n");
}
/// Reordonam punctele in ordinea corecta a infasuratorii convexe
u[0] = p[0];
i = 0;
while(v[i].minus)
i ++;
j = 1;
while(i < n-1){
u[j] = v[i].end;
i ++;
j ++;
}
i = 0;
while(j < n){
u[j] = v[i].end;
i ++;
j ++;
}
if(DEBUG){
for(i = 0; i < n; i ++){
printf("%d ", u[i].id);
}
printf("\n");
}
// Determinam infasuratoarea convexa
r[0] = u[0];
r[1] = u[1];
dr = 2;
for(i = 2; i < n; i ++){
while(dr > 1 && getOrder(r[dr - 2], r[dr - 1], u[i]) != -1)
dr --;
r[dr] = u[i];
dr ++;
}
if(DEBUG){
for(i = 0; i < dr; i ++){
printf("%d ", r[i].id);
}
printf("\n\n");
}
// Determinam dreptunghiul minim care sa contina infasuratoarea convexa
Edge base;
Point prj;
Point minxi, maxxi;
min = (maxx - minx) * (maxy - miny);
for(i = 0; i < dr; i ++){
minx = MAXVAL;
maxx = -MAXVAL;
maxd = 0;
base = getEdge(r[i], r[(i + 1) % dr]); // Luam latura de baza
if(DEBUG)
printf("%d - %d:\n", r[i].id, r[(i + 1) % dr].id);
if(base.a != MAXVAL && base.a != 0){
for(j = 0; j < dr; j ++){
prj = getProjection(r[j], base);
if(DEBUG)
printf("proiectie %d - (%.2f, %.2f)\n", r[j].id, prj.x, prj.y);
if(prj.x < minx){
minx = prj.x;
minxi = prj;
}
if(prj.x > maxx){
maxx = prj.x;
maxxi = prj;
}
dist = getDistance(prj, r[j]);
if(dist > maxd)
maxd = dist;
}
// Dist este aria
dist = maxd * getDistance(maxxi, minxi);
if(min == -1 || min > dist)
min = dist;
if(DEBUG)
printf("%.2f = %.2f * %.2f\n\n", dist, maxd, getDistance(maxxi, minxi));
}
}
ofstream fout ("rubarba.out");
fout << fixed;
fout << setprecision(2);
fout << min << endl;
fout.close();
return 0;
}