Pagini recente » Borderou de evaluare (job #2467446) | Borderou de evaluare (job #2467415) | concurs-algorithm | Monitorul de evaluare | Cod sursa (job #3354653)
//sursa neterminata
#include <fstream>
#include <algorithm>
using namespace std;
struct ura{
double x, y;
bool parte; ///true pentru dr-jos, false pentru st-sus
} v[120001], st[120001];
ura pct1[120001], pct2[120001]; ///partea true, respectiv partea false
bool cmp( ura a, ura b ){
if( a.x < b.x )
return true;
if( a.x > b.x )
return false;
if( a.y < b.y )
return true;
return false;
}
double arie( double x1, double y1, double x2, double y2, double x3, double y3 ){
return (x1*y2+x2*y3+x3*y1-x3*y2-x1*y3-x2*y1)/2;
} ///functia returneaza aria unui triunghi
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int main()
{
int n, i;
cin>>n;
for( i = 1; i <= n; i++ ){
cin>>v[i].x>>v[i].y;
///aducem fiecare element in cadranul 1
v[i].x+=1000000000;
v[i].y+=1000000000;
}
sort( v + 1, v + n + 1, cmp );
///determinam partea fiecarui element
//v[1] si v[n] sunt exceptiile, fiind in ambele parti simultan
int x1=v[1].x, y1=v[1].y, x2=v[n].x, y2=v[n].y;
for( i = 2; i <= n - 1; i++ ){
///dreapta AB; A(x1,y1) si B(x2,y2)
//daca aria < 0 atunci e in dr/josul liniei
//aria != 0 pentru ca nu exista puncte coliniare
//daca aria > 0 atunci e in st/susul liniei
if( arie(x1,y1,x2,y2,v[i].x,v[i].y) < 0 )
v[i].parte=true;
else
v[i].parte=false;
}
///acum facem partea true ( dr-jos ), punand punctele in vectorul pct1[]
v[n].parte=true;
st[1]=v[1];
i=2;
while( v[i].parte == false && i <= n - 1 )
i++;
if( i != n )
st[2]=v[i];
int k=2;
for( i = i + 1; i <= n - 1; i++ )
if( v[i].parte == true ){
x1=v[k-1].x;
y1=v[k-1].y;
x2=v[k].x;
y2=v[k].y;
while( arie(x1,y1,x2,y2,v[i].x,v[i].y) < 0 && k >= 2 ){
k--;
if( k >= 2 ){
x1=v[k-1].x;
y1=v[k-1].y;
x2=v[k].x;
y2=v[k].y;
}
}
st[++k]=v[i];
}
return 0;
}