ИМНО, проще находить отражение так: пусть исходная точка (x0,y0), новая (x1,y1). Тогда
a*x1+b*y1=-a*x0-b*y0-2*c,
-b*x1+a*y1=-b*x0+a*y0.
Решаешь эту систему, получаешь ответ.
1 2009-12-01 18:15:41
Re: informatic.mccme.ru (Geometry) (5 ответов, оставленных в Problems)
2 2009-11-27 16:25:33
Re: informatics.mccme.ru (5 ответов, оставленных в Problems)
Замени в функции Normal return
Line(p,p-norm);на
return Line(p,p+norm);Также лучше удалить строки
if ((p-p1).scal(norm) < 0) norm.x*=-1,norm.y*=-1;
norm.makeLen(Line(p1,p2).dist(p));, потому что так будет меньше погрешность.
3 2009-11-25 11:35:56
Re: informatics.mccme.ru (5 ответов, оставленных в Problems)
Строим 2 прямых, которые перпендикулярны сторонам и проходят через противоволожные стороне точкам
И находим пересечение этих прямых.
Там же точка пересечения медиан. http://ru.wikipedia.org/wiki/Медиана_треугольника
4 2009-11-16 17:08:42
Тема: Timus 1695 (1 ответов, оставленных в Problems)
http://acm.timus.ru/problem.aspx?space=1&num=1695
Добрый день! Кто-нибудь знает быстрый алгоритм для решения этой задачи? Сам я ее недавно решил, теперь хотелось бы улучшить результат.
5 2009-10-29 16:40:53
Re: Vengerskiy Algoritm za O(n^3) (4 ответов, оставленных в Algo)
Я знаю, просто предупредил на всякий случай 
6 2009-10-29 11:56:22
Re: Vengerskiy Algoritm za O(n^3) (4 ответов, оставленных в Algo)
Когда то писал эту задачу, код сохранился. По моему, он решает не на минимум, а на максимум, но за O(N^3)
#include <cstdio>
#include <cstring>
const int MAX=701;
int a[MAX][MAX];
int n;
int x[MAX], y[MAX], sx[MAX], sy[MAX], mx[MAX], my[MAX];
inline int get(int x,int y)
{
return a[x][y]-mx[x]-my[y];
}
bool go(int cur)
{
sx[cur]=1;
for(int i=0;i<n;i++)
{
if(get(cur,i)==0)
{
if(y[i]==-1)
{
sy[i]=cur;
while(1)
{
int t=x[cur];
x[cur]=i;
y[i]=cur;
if(~t)
{
cur=sy[t];
i=t;
}
else break;
}
return true;
}
}
}
for(int i=0;i<n;i++)
{
if(get(cur,i)==0)
{
if(!sx[y[i]])
{
sy[i]=cur;
if(go(y[i]))
{
return true;
}
}
}
}
return false;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
mx[i]=-50000;
for(int j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]>mx[i])mx[i]=a[i][j];
}
}
for(int i=0;i<n;i++)
{
int m=-50000;
for(int j=0;j<n;j++)
{
int t=get(j,i);
if(t>m)m=t;
}
my[i]=m;
}
memset(x,-1,sizeof x);
memset(y,-1,sizeof y);
for(int sc=0;sc<n;sc++)
{
memset(sx,0,sizeof sx);
memset(sy,-1,sizeof sy);
bool b=go(sc);
while(!b)
{
int m=-50000, dx;
for(int i=0;i<n;i++)
{
if(sx[i])
{
for(int j=0;j<n;j++)
{
if(!(~sy[j]))
{
int t=get(i,j);
if(m<t)
{
m=t;
dx=i;
}
}
}
}
}
for(int i=0;i<n;i++)
{
if(sx[i])mx[i]+=m;
if(~sy[i])my[i]-=m;
}
b=go(dx);
}
}
for(int i=0;i<n;i++)
{
printf("%d ",x[i]+1);
}
}7 2009-10-05 09:43:01
Re: Динамика по профилю. Задача "паркет" (13 ответов, оставленных в Algo)
Oleg пишет:
Кстати доминошную динамику можно реализовать и за O(M*N*M^2)
А как?
8 2009-09-15 15:42:20
Re: Задача с 5-ого Открытого Кубка (10 ответов, оставленных в Problems)
shtserg пишет:
Мне рассказывали сдавшие её тогда люди, что в качестве ответа подходит что то вроде (t,t^2,t^3,t^4) для различных t. И что это всё следует из какой-то глубокой теории, которая им была известна. Сомневаюсь, что кто-то решал эту задачу так, как предлагалось на разборе
Да, тоже верное решение. Это следует из того, что определитель Вандермонда никогда не равен нулю. В принципе, если догадаться, что никакие 5 точек не должны лежать в одном 3-х мерном пространстве, то такое решение становится почти очевидным. а насчет сферы- по моему можно обойтись без проверки, ведь вероятность, что из случайно сгенерированных 10 точек какие либо 5 лежат в одном пространстве крайне мала.
9 2009-09-12 13:06:18
Re: Задача с 5-ого Открытого Кубка (10 ответов, оставленных в Problems)
мы знаем, что 5 ребер не могут быть линейно независимые в 4-х мерном пр-ве => одно какое-то может быть представлено через другие 4. Тогда одно из ребер будет находиться внутри фигуры, и не являться необходимым для построения фигуры
Неверно. Из линейной независимости не следует что ребро обязательно лежит внутри. И вообще, следуя этим рассуждениям, можно получить, что в 3-мерном пространстве существуют только 4-вершинные выпуклые многогранники
10 2009-09-11 10:42:29
Re: Задача с 5-ого Открытого Кубка (10 ответов, оставленных в Problems)
Если я правильно понял задачу, то по моему достаточно взять n точек на 4-мерной сфере, если n>4, а иначе вывести "нет решения"