Contest.uni-smr.ac.ru :: Programming contests in Samara
Русская версия || English version
Login:
Password:
Forget password?
 example: Bill Gates
 






Forum

ТемаАвтор Время
Задача J - говно. Контест - говно. dalex 06.04.2014 13:12
И те, кто отвечали на клары - тоже молодцы. dalex 06.04.2014 13:14
= DK 07.04.2014 01:07
Вот ответь мне, только да или нет

Почему нельзя начать разгружать на кране G в момент времени 48, и закончить в момент времени 65? На отрезке 48-62 делаем 14 разгрузок, и в момент времени 65 - заканчиваем последнюю. Это дает ответ 66 - 48 = 17, что лучше, чем у жюри.
плюс school14_315 27.09.2014 11:20
поддерживаю
Че не раьотает? pytonc++ 25.01.2015 21:37
const ld eps = 1e-9;

struct vect { // Вектор
ld x, y, z;
vect(){}
vect(ld x, ld y, ld z) : x(x), y(y), z(z){}
vect(vect s, vect t) : x(t.x - s.x), y(t.y - s.y), z(t.z - s.z){}
void scan(){
scanf("%Lf %Lf %Lf", &x, &y, &z);
}
vect operator + (vect s){
return vect(x + s.x, y + s.y, z + s.z);
}
vect operator - (vect s){
return vect(x - s.x, y - s.y, z - s.z);
}
vect operator * (ld t){
return vect(x*t, y*t, z*t);
}
};

inline ld sq(ld a){
return a * a;
}

ld len_v(vect s){ // Длина вектора
return sqrt(sq(s.x) + sq(s.y) + sq(s.z));
}

vect norm(vect s){ // Нормировать вектор
return s * (1 / len_v(s));
}

vect ort(vect s, vect t){ // Перпендикулярный вектор двум векторам
return vect(s.y*t.z - s.z*t.y, s.z*t.x - s.x*t.z, s.x*t.y - s.y*t.x);
}

ld d_prod(vect s, vect t){
return s.x*t.x + s.y*t.y + s.z*t.z;
}

ld c_prod(vect s, vect t){
return len_v(ort(s, t));
}

struct line { // Прямая
vect s, v;
line(){}
line(vect s, vect t) : s(s), v(norm(t - s)){}
};

struct plane { // Плоскость
vect s, n;
plane(){}
plane(vect a, vect b, vect c) : s(a), n(norm(ort(vect(a, b), vect(a, c)))){}
};

ld dist(vect p, plane alp){ // Расстояние от точки до плоскости
return abs(d_prod(vect(alp.s, p), alp.n));
}

ld dist(vect t, vect s){ // Расстояние от точки до точки
return sqrt(sq(s.x - t.x) + sq(s.y - t.y) + sq(s.z - t.z));
}

ld dist(vect s, line a){ // Расстояние от точки до прямой
return abs(c_prod(vect(a.s, s), a.v));
}

ld dist(line a, line b){ // Расстояние между прямыми
if (abs(c_prod(a.v, b.v)) < eps){
return dist(a.s, b);
}
plane alp(a.s, a.s + a.v, a.s + b.v);
return dist(b.s, alp);
}

bool on_line(vect s, line a){
return abs(c_prod(vect(a.s, s), a.v)) < eps;
}

vect l_vs_l(line a, line b){ // Точка пересечения двух прямых
ld t = c_prod(b.v, b.s - a.s) / c_prod(b.v, a.v);
vect dif = a.v * t, M1 = a.s + dif, M2 = a.s - dif;
if (on_line(M1, a) && on_line(M1, b)){
return M1;
}
return M2;
}

vect proec(vect s, plane alp){ // Проекция точки на плоскость
ld d = dist(s, alp);
vect dif = alp.n * d, M1 = s + dif, M2 = s - dif;
if (dist(M1, alp) < eps){
return M1;
}
return M2;
}

vect l_vs_pl(line a, plane alp){ // Пересечение прямой с плоскостью
vect A = proec(a.s, alp), B = proec(a.s + a.v, alp);
return l_vs_l(a, line(A, B));
}

void print(vect a){
cout << a.x << " " << a.y << " " << a.z << endl;
}

// ----------------------------------------------------------------

const ld eps = 1e-9, pi = acos(-1.0), inf = 1e9;

struct vect {
ld x, y;
vect(){}
vect(ld x, ld y) : x(x), y(y){}
vect(vect s, vect t) : x(t.x - s.x), y(t.y - s.y){}
void scan(){
scanf("%Lf %Lf", &x, &y);
}
vect operator + (vect s){
return vect(x + s.x, y + s.y);
}
vect operator - (vect s){
return vect(x - s.x, y - s.y);
}
vect operator * (ld t){
return vect(x * t, y * t);
}
};

ld c_prod(vect s, vect t){
return s.x*t.y - s.y*t.x;
}

ld d_prod(vect s, vect t){
return s.x*t.x + s.y*t.y;
}

ld len_v(vect s){
return hypot(s.x, s.y);
}

ld dist(vect s, vect t){
return hypot(s.x - t.x, s.y - t.y);
}

vect mid(vect s, vect t){
vect dif(s, t);
return s + dif * 0.5;
}

vect ort(vect s){
return vect(-s.y, s.x);
}

vect p[N], st;

bool operator < (vect s, vect t){
vect v1(st, s), v2(st, t);
ld cp = c_prod(v1, v2);
if (abs(cp) < eps){
return len_v(v1) < len_v(v2);
}
return cp > 0;
}

int main(){
#ifdef local
freopen(task ".in", "r", stdin);
freopen(task ".out", "w", stdout);
#endif

cout << fixed;
cout.precision(3);

int n, i, k;

cin >> n;
st = vect(inf, inf);
for (i = 0; i < n; i++){
p[i].scan();
if (p[i].x < st.x || (abs(p[i].x - st.x) < eps && p[i].y < st.y)){
st = p[i];
}
}

sort(p, p + n);

vector<vect> poly = {p[0], p[1]};
for (i = 2; i < n; i++){
for (k = poly.size() - 1; k && c_prod(vect(poly[k], p[i]), vect(poly[k], poly[k - 1])) < eps; k--){
poly.pop_back();
}
poly.push_back(p[i]);
}

for (i = 0; i < poly.size(); i++){
cout << poly[i].x << " " << poly[i].y << endl;
}

return 0;
}


You must be logged in to post messages to this forum.