Cod sursa(job #842116)

Utilizator andreea29Iorga Andreea andreea29 Data 26 decembrie 2012 09:37:32
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.3 kb
#include<fstream> 
#include<algorithm> 
#include<cmath> 
#include<iostream> 
   
#define Nmax 100010 
#define INFI 0x3f3f3f3f 
   
using namespace std; 
   
int n, st[Nmax], viz[Nmax], k; 
   
struct punct { 
    int x; 
    int y; 
} p[Nmax]; 
   
int cmp (punct a, punct b) 
{ 
    if (a.x > b.x) 
        return 0; 
    if (a.x == b.x && a.y > b.y) 
        return 0; 
    return 1; 
} 
   
double det (punct a, punct b, punct c) 
{ 
    return (b.x * c.y + c.x * a.y + a.x * b.y) - (a.y * b.x + b.y * c.x + c.y * a.x); 
} 
   
int semn (punct a, punct b, punct c) 
{ 
    double d = det (a, b, c);
	if(fabs(d) < 0.0000000001) 
		return 0;
	if (d > 0)
        return 1;
	else
        return 2;
} 
   
void convex () 
{ 
	st[0] = 0;
    st[1] = 1;
    st[2] = 2;
    viz[1] = viz[2] = 1;
    int s = 1; //semn (p[0], p[1], p[2]);
    k = 2;
    int i = 3;
    while (i < n)
    {
        int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        while (s != s1 && s1 != 0)
        {
            viz[st[k]] = 0;
            --k;
            s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        }
        ++k;
        st[k] = i;
        viz[i] = 1;
        ++i;
    }
    --i;
    while (i >= 0)
    {
        while (viz[i] && i >= 0)
            --i;
        if (i < 0)
            break;
        int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        while (s != s1 && s1 != 0)
        {
            --k;
            s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        }
        ++k;
        st[k] = i;
        --i;
    }

} 
   
double dist (int i, int j) 
{ 
    return sqrt(double(((p[i].x - p[j].x) * (p[i].x - p[j].x)) + ((p[i].y - p[j].y) * (p[i].y - p[j].y)))); 
} 
   
   
double proiectie (int i, int j, int k) 
{ 
    double ar = det (p[i], p[j], p[k]); 
    ar = abs(ar); 
    return ar / dist (i, j); 
} 
   
double amax (int i1, int i2) 
{ 
    double maxh = -1; 
    double d1, d2; 
    double max1 = 0; 
    double max2 = 0; 
    double da = dist (i1, i2); 
    for (int i = 0; i < k; ++i) 
    { 
        if (st[i] != i1 && st[i] != i2) 
        { 
			double pr = proiectie (i1, i2, st[i]); 
            if (pr > maxh) 
                maxh = pr; 
            d1 = dist (i1, st[i]); 
            d2 = dist (i2, st[i]); 
            d1 = sqrt (double (d1 * d1 - pr * pr)); 
            d2 = sqrt (double (d2 * d2 - pr * pr)); 
            if (d1 > da && d2 > max2) 
                max2 = d2; 
            else
                if (d2 > da && d1 > max1) 
                    max1 = d1; 
        } 
    } 
    return maxh * (max2 + max1 + da); 
} 
   
int main() 
{ 
    ifstream f("rubarba.in"); 
    ofstream h("rubarba.out"); 
    f >> n; 
    for (int i = 0; i < n; ++i) 
    { 
        f >> p[i].x >> p[i].y; 
    } 
    f.close(); 
   
    sort(p, p + n, cmp); 
   
    convex (); 
   
    double minim = INFI; 
   
    for (int i = 0; i < k; ++i) 
    { 
        double blabla = amax (st[i], st[i + 1]); 
        if (blabla < minim) 
            minim = blabla; 
       // cout << blabla << '\n'; 
    } 
   
    //for (int i = 0; i < k; ++i) 
        //h << st[i] << " "; 
   
    minim = (int (minim * 100)); 
    minim = minim / 100; 
   
    h << minim << '\n'; 
   
    h.close(); 
    return 0; 
}