ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1103. Карандаши и окружности

I think that test data is incorrect. There is a test where there is four points on one circle!!!
Послано Nikolay Marinov 1 фев 2003 19:14
This is my source : I think everything is correct!!!

#include <fstream.h>
#include <stdlib.h>
#include <math.h>
#include <iomanip.h>

  struct TPoint
    {double x, y;};

  struct TAngle
    {
      double ang;
      int ind;
    };

  TPoint A[5100];
  TAngle B[5100];
  int n;
  double min;
  int ind;
  TPoint tmp;

  void ReadData ()
    {
      cin >> n;
      for (int i = 0; i <= n - 1; i++)
        {cin >> A[i].x >> A[i].y;}
    }

  double dist (TPoint const &a, TPoint const &b)
    {return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));}

  int comp (const void *e1, const void *e2)
    {
      double z = ((TAngle*)e1)->ang - ((TAngle*)e2)->ang;
      if (z < 0)
        return -1;
      if (z > 0)
        return 1;
      if (z == 0)
        while (1) // Here if there is four points on one circle
program gets TL...
          {}
    }

  void Solve ()
    {
      min = A[0].y;
      ind = 0;
      for (int i = 1; i <= n - 1; i++)
        if (A[i].y < min)
          {
            min = A[i].y;
            ind = i;
          }
      tmp = A[0];
      A[0] = A[ind];
      A[ind] = tmp;
      min = atan2 (A[1].y - A[0].y, A[1].x - A[0].x)*1000;
      ind = 1;
      for (int i = 2; i <= n - 1; i++)
        if (atan2 (A[i].y - A[0].y, A[i].x - A[0].x)*1000 < min)
          {
            min = atan2 (A[i].y - A[0].y, A[i].x - A[0].x)*1000;
            ind = i;
          }
      tmp = A[1];
      A[1] = A[ind];
      A[ind] = tmp;
      double a, b, c;
      for (int i = 2; i <= n - 1; i++)
        {
          B[i].ind = i;
          a = dist (A[0], A[i]);
          b = dist (A[1], A[i]);
          c = dist (A[0], A[1]);
          B[i].ang = acos ((a*a + b*b - c*c)/(2*a*b));
          B[i].ang *= 1000;
        }
      qsort (&B[2], n - 2, sizeof (TAngle), comp);
    }

  void WriteData ()
    {
      cout << setiosflags (ios::fixed) << setprecision (0) << A[0].x
<< " " << A[0].y << endl;
      cout << setiosflags (ios::fixed) << setprecision (0) << A[1].x
<< " " << A[1].y << endl;
      cout << setiosflags (ios::fixed) << setprecision (0) << A[B[(1
+ n)/2].ind].x << " " << A[B[(1 + n)/2].ind].y << endl;
    }

  int main ()
    {
      ReadData ();
      Solve ();
      WriteData ();
      return 0;
    }
Re: I think that test data is incorrect. There is a test where there is four points on one circle!!!
Послано Locomotive 1 фев 2003 19:32
how you find testdata?????
Re: I think that test data is incorrect. There is a test where there is four points on one circle!!!
Послано Nikolay Marinov 2 фев 2003 00:53
when i sort points i add to my source while (1) {} if there is four
point on one circle so my program to get TL. And it gets it... so
there is test case where there is four points on one circle ...
TOO interesting!!!
Послано Locomotive 2 фев 2003 19:55
Then which one it is?
Послано charles.king 27 апр 2004 09:53
Incorrect method
Послано Vlad Veselov 27 апр 2004 17:56
Maybe your program really works very slow, better use MLE or some Crash to find incorrect tests.
What the right methon?
Послано tbtbtb 27 апр 2004 18:04
Example of MLE routine.
Послано Vlad Veselov 27 апр 2004 22:51
Those you can emulate MLE:
Procedure MakeMLE;
 Begin
  MakeMLE;
 End;

Those you can emulate OLE:
Procedure MakeOLE;
 Begin
  While True Do WriteLn;
 End;