http://acm.sgu.ru/problem.php?contest=0&problem=256
podskajite kak mojno reshit etu zada4u , pridumal tolko dinamiku za O(5^n*m);
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Сообщения от Rasul Abdulaev
http://acm.sgu.ru/problem.php?contest=0&problem=256
podskajite kak mojno reshit etu zada4u , pridumal tolko dinamiku za O(5^n*m);
Где можно почитать ?
незнаю линейную программирование!!!!!))) Без этого невзя ?
http://acm.sgu.ru/problem.php?contest=0&problem=206
Как можно решить эту задачу))) незнаю линейную программирование
для кругов . я свел вторую задачу на первую
Все в месте ... n <= 50000
Даны n окружности. Определить пересекаются ли окружности.
Вторая задача.
Минимальная окружность, покрывающая множество точек
как можно решить такую задачу ?
http://acm.sgu.ru/problem.php?contest=0&problem=138
Кто знаеть теория Смита?
или где можно посчитать ?
ooo interesnaya zada4a. i kak mojno rewit ?
po4emu tolko dlya vzaimno prostih a i m
a^(n*p-q) mod m = b mod m
( a^(n*p)*a^(-q) ) mod m = b mod m
(a^(n*p) * a ^ (-q) * a^q) mod m = (b * a^q) mod m
razve ne dlya vseh a i m?
Mojno li za O(Koli4est4o deliteli 4isla n) naiti vse deliteli 4isla n? ili Za skolko mojno naiti?))))))))
unsigned long long gcd (unsigned long long a,unsigned long long b,unsigned long long & x,unsigned long long & y)
{
if (a == 0)
{
x = 0; y = 1;
return b;
}
unsigned long long x1, y1;
unsigned long longd = gcd (b%a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}
(b/a)*x1 -> zdes perepolnenii nebudet?
Net imenno delenie nado!!!! i tam vsegda u menya ne4etnoe 4islo.
a*x+2^64*y=1
a=31^k (t.e a yavlyaetsya stepenuy 31).izpolzuya eti informacii, dumau zdes mojno cheto pridumat!!!
Ya nashel hash ot podstroki . I mne nado podelit !!! Chto by podelit nado obratniy element po modulu!!!!
a*x=1(mod 2^64) gde x=a^-1
a*x + 2^64*y = 1!!! U menya problema ,kak predstavit 2^64? Ved' 2^64 nezya predstavit vide unsigned long long !!!
блииин тупая ошибка
if (norm.scal(p1) < 0) norm.x*=-1,norm.y*=-1;
изменил на
if (norm.scal(p-p1) < 0) norm.x*=-1,norm.y*=-1;
спасибо всемммм. Но лучше через уравнение . Код получается короче.
Это Мой Код . И Там другая задача . а это другая .
Постройте отражение
Заданы коэффициенты уравнения прямой a, b и с и координаты точки A (xa, ya). Найдите точку A’, которая является отражением точки A относительно заданной прямой.
Исходные данные: в начале с клавиатуры вводятся коэффициенты уравнения прямой, затем координаты точки A. Исходные данные являются целыми числами, по модулю не превышающими 1000
Результат: выведите координаты точки A’ с точностью до пятого знака после запятой.
input #1
1 0 0 3 1
output #1
-3 1
input #2
1 -1 0 1 0
output #2
0 1
#include <iostream>
#include <cmath>
using namespace std;
struct Point {
double x,y;
Point()
{
x=y=0;
}
Point(double xx,double yy)
{
x=xx;
y=yy;
}
void read()
{
scanf("%lf%lf",&x,&y);
}
Point operator-(Point a)
{
return Point(x-a.x,y-a.y);
}
double operator*(Point a)
{
return x*a.y-y*a.x;
}
double scal(Point a)
{
return x*a.x+y*a.y;
}
void makeLen(double l)
{
double dist = sqrt(x*x+y*y);
x*=l/dist;
y*=l/dist;
}
};
double a,b,c;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%lf%lf%lf",&a,&b,&c);
Point p ;
p.read();
double l = fabs(a*p.x+b*p.y+c)/sqrt(a*a+b*b);
Point norm = Point(a,b);
Point p1;
if (a!=0) p1= Point(-c/a,0); else
p1 = Point(0,-c/b);
if (norm.scal(p1) < 0 ) norm.x*=-1,norm.y*=-1;
norm.makeLen(l);
Point p2 = p - norm;
printf("%.5lf %.5lf",p2.x - norm.x , p2.y-norm.y);
return 0;
}
Помогите плз , WA #3 тест. Че за проблема . Я думаю ошибка из за погрешности.
Спасибо. Ошибка из за погрешности .
if ((p-p1).scal(norm) < 0) norm.x*=-1,norm.y*=-1;
norm.makeLen(Line(p1,p2).dist(p));
убрал ACCEPTED!!!!
http://informatics.mccme.ru/moodle/mod/ … pterid=440
ой , сорри сылку неправильно дал
http://informatics.mccme.ru/moodle/mod/ … pterid=440
#include <iostream>
#include <cmath>
using namespace std;
struct Point {
double x,y;
Point()
{
x=y=0;
}
Point(double xx,double yy)
{
x=xx;
y=yy;
}
void read()
{
scanf("%lf%lf",&x,&y);
}
void write()
{
printf("%.6lf %.6lf\n",x,y);
}
Point operator-(Point a)
{
return Point(x-a.x,y-a.y);
}
double operator*(Point a)
{
return x*a.y-y*a.x;
}
double scal(Point a)
{
return x*a.x+y*a.y;
}
double dist()
{
return sqrt(x*x+y*y);
}
double dist(Point p)
{
return sqrt((p.x-x)*(p.x-x)+ (p.y-y)*(p.y-y));
}
void makeLen(double l)
{
double dist = sqrt(x*x+y*y);
x*=l/dist;
y*=l/dist;
}
};
struct Line {
double a,b,c;
Line()
{
a=b=c=0;
}
Line(double aa,double bb,double cc)
{
a=aa;b=bb;c=cc;
}
Line(Point p1,Point p2)
{
a=p2.y-p1.y;
b=p1.x-p2.x;
c=-(a*p1.x+b*p1.y);
}
Point Intersec(Line l)
{
Point p = Point((b*l.c-l.b*c)/(a*l.b-l.a*b) , -(a*l.c-l.a*c)/(a*l.b-l.a*b));
return p;
}
double dist(Point p)
{
return abs(a*p.x+b*p.y+c)/sqrt(a*a+b*b);
}
};
Line Normal(Point p,Point p1,Point p2)
{
Point norm = Point(Line(p1,p2).a,Line(p1,p2).b);
if ((p-p1).scal(norm) < 0) norm.x*=-1,norm.y*=-1;
norm.makeLen(Line(p1,p2).dist(p));
return Line(p,p-norm);
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
Point p1,p2,p3;
p1.read();p2.read();p3.read();
Line l1 = Normal(p1,p2,p3);
Line l2 = Normal(p2,p1,p3);
Point p = l1.Intersec(l2);
p.write();
}
vrode vse pravilno. No WA6 test. Pomogite plz.
Idea:
Строим 2 прямых, которые перпендикулярны сторонам и проходят через противоволожные стороне точкам
И находим пересечение этих прямых.
Plz , скинте реализацию Венгерского алгоритма за O(n^3).
vot my krasim verchiniy.
X+ X- Y+ Y-
:)
Y+ Y-
----------------
x+ | | -z
X- | +z|
z = min(a i,j) gde i in X+ , j in Y- ,da?
a u vas eto ne tak mne kajetsya
if (vx[i]) minrow[i] += z;
if (vy[i]) mincol[i] -= z;
a mne kajetsya doljno byt
if (vx[i]) minrow[i] -= z;
if (vy[i]) mincol[i] += z;
v 4em u menya owibka?
MAXimal :: φορυμ » Сообщения от Rasul Abdulaev