Cod sursa(job #834483)

Utilizator andreea29Iorga Andreea andreea29 Data 14 decembrie 2012 14:45:06
Problema Rubarba Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.28 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; 
} 
  
float 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) 
{ 
    float d; 
    d = det (a, b, c); 
    if (d > 0) 
        return 1; 
    else
		if (d < 0)
			return -1;
		else
			return 0;
} 
  
void convex () 
{ 
    int i; 
    st[0] = 0; 
    st[1] = 1; 
    st[2] = 2; 
    viz[1] = viz[2] = 1; 
    k = 2; 
    i = 3; 
    int s = semn (p[st[0]], p[st[1]], p[st[2]]); 
	if (s == 0)
		s = 1;
    while (i < n) 
    { 
		float 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 (st[k] != 0) 
    { 
        while (viz[i]) 
            i--; 
		float 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; 
    } 
} 
  
float 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)))); 
} 
  
  
float proiectie (int i, int j, int k) 
{ 
    float ar = det (p[i], p[j], p[k]); 
    ar = abs(ar); 
    return ar / dist (i, j); 
} 
  
float amax (int i1, int i2) 
{ 
    float maxh = -1; 
    float d1, d2; 
    float max1 = 0; 
    float max2 = 0; 
    float da = dist (i1, i2); 
    for (int i = 0; i < k; ++i) 
    { 
        if (st[i] != i1 && st[i] != i2) 
        { 
            float 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 (); 
  
    float minim = INFI; 
  
    for (int i = 0; i < k; ++i) 
    { 
        float 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; 
}