ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1103. Pencils and Circles

I think that test data is incorrect. There is a test where there is four points on one circle!!!
Posted by Nikolay Marinov 1 Feb 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!!!
Posted by Locomotive 1 Feb 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!!!
Posted by Nikolay Marinov 2 Feb 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!!!
Posted by Locomotive 2 Feb 2003 19:55
Then which one it is?
Posted by charles.king 27 Apr 2004 09:53
Incorrect method
Posted by Vlad Veselov 27 Apr 2004 17:56
Maybe your program really works very slow, better use MLE or some Crash to find incorrect tests.
What the right methon?
Posted by tbtbtb 27 Apr 2004 18:04
Example of MLE routine.
Posted by Vlad Veselov 27 Apr 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;