Такого рода задачи бывают олимпиадными, и у них оговаривается ввод. У Вас как?

Согласен, что программа не на школьном уровне. У меня ввод не оговаривался, возможно входные данные могут быть случайными.
Если можно, то хотя бы примерное написание программы подскажите.

LfiN:
Добрый день, LfiN!
Источник: http://algolist.manual.ru/olimp/geo_sol.php#a9

Один из возможных методов решения. Предположим, мы нашли такую прямую. Будем сдвигать ее в направлении, перпендикулярном этой прямой (параллельный перенос) до тех пор, пока она не пересечет какую-нибудь из концевых точек отрезка. За счет поворота прямой вокруг этой точки мы можем добиться того, что прямая будет проходить через 2 концевые точки отрезков и не перестанет быть решением задачи.

Следовательно, мы должны рассмотреть прямые, проходящие через все возможные комбинации пар концевых точек отрезков. Всего надо проверить (2*N-1)+(2*N-2)+...+1=N*(2*N-1) линий и для каждой из них найти число пересечений с отрезками. Та прямая, у которой это число максимальное, и есть искомая.

При решении возникает подзадача.

Определить, пересекается ли прямая ax+b=y и отрезок с концами (x1,y1), (x2,y2).


Решение ее.
Вариант 1. Можно через концы отрезка провести прямую cx+d=y и определить, принадлежит ли точка пересечения двух прямых x, если она существует, отрезку. То есть, мы должны решить уравнение x*(c-a)=(b-d), найти y=ax+b, и проверить выполнение неравенств x1<=x<=x2, y1<=y<=y2.

Но при нахождении x при делении могут возникнуть большие вычислительные погрешности или даже переполнение или потеря значимости, в результате чего получится неверный ответ.

Вариант 2. Обозначим F(x,y)=ax+b-y. Прямая ax+b=y разбивает плоскость на три части: в одной F(x,y)>0, в другой F(x,y)<0 и на прямой ax+b=y F(x,y)=0 . Если эта прямая пересекает отрезок, то либо концы отрезка лежат в различных полуплоскостях, либо хотя бы одна концевая точка отрезка лежит на прямой. Это равносильно выполнению следующего неравенства F(x1,y1)*F(x2,y2)<=0. Таким образом, не вычисляя точку пересечения, мы по знаку функционала судим о том, имеют ли прямая и отрезок общую точку. Очевидно, что второй вариант решения подзадачи предпочтительнее первого.

Решение:

#include <iostream>
using namespace std;
const int n=20;
struct line
{
int x1,y1,x2,y2;
};

int main()
{
int i,j;
int num_intersect[n][n];//номер отрезка;пересечен ли с другим отрезком. 1-да,0-нет
line obj[n];
int count=0;//число пересечений
int num=0;//номер отрезка у которого больше всего пересечений

for(i=0;i<n;i++)//случайным образом для каждого отрезка задаем координаты и печатаем их
{
obj[i].x1=rand()%100;
obj[i].y1=rand()%100;
obj[i].x2=rand()%100;
obj[i].y2=rand()%100;
cout<<"("<<obj[i].x1<<","<<obj[i].y1<<");("<<obj[i].x2<<","<<obj[i].y2<<")\n";
}

for(i=0;i<n;i++)//по всем отрезкам
{
int cnt=0;
for(j=0;j<n;j++)//каждый отрезок сравниваем со всеми другими и выясняем пересекаются они или нет
{
if(i==j)
{
num_intersect[i][j]=0;
continue;
}
int v1=(obj[j].x2-obj[i].x1)*(obj[i].y1-obj[j].y1)-(obj[j].y2-obj[j].y1)*(obj[i].x1-obj[j].x1);
int v2=(obj[j].x2-obj[i].x1)*(obj[i].y2-obj[j].y1)-(obj[j].y2-obj[j].y1)*(obj[i].x2-obj[j].x1);
int v3=(obj[i].x2-obj[i].x1)*(obj[j].y1-obj[i].y1)-(obj[i].y2-obj[i].y1)*(obj[j].x1-obj[i].x1);
int v4=(obj[i].x2-obj[i].x1)*(obj[j].y2-obj[i].y1)-(obj[i].y2-obj[i].y1)*(obj[j].x2-obj[i].x1);
if((v1*v2<0) && (v3*v4<0))
{
num_intersect[i][j]=1;
cnt++;
}
else
num_intersect[i][j]=0;
}

if(count<cnt)//если мы найдем отрезок у которого больше всего пересечений запоминаем его номер и число пересечений
{
num=i;
count=cnt;
}
}
cout<<endl<<endl;
cout<<"line: "<<num<<" count: "<<count<<"| ";//печатаем номер отрезка у которого больше всего пересечений,число пересечений,координаты
cout<<"("<<obj[num].x1<<","<<obj[num].y1<<");("<<obj[num].x2<<","<<obj[num].y2<<")\n\n";
for(i=0;i<n;i++)//печатаем номер и координаты отрезков с которыми пересекается найденный нами
{
if(num_intersect[num][i]==1)
{
cout<<"num line: "<<i<<"| ";
cout<<"("<<obj[i].x1<<","<<obj[i].y1<<");("<<obj[i].x2<<","<<obj[i].y2<<")\n";
}
}
return 0;
}