Area of a Polygon: the Most Comic Code I’ve Ever Seen

When I was a freshman, I took part in a programming contest for students.

One task was quite typical: a text file contains vertices of a polygon; the program must print its area. Input format:

0 or 1 (clockwise or counterclockwise)
x1 y1
x2 y2
...
xN yN

Output format is a big tricky: the result must rounded without  round half to even rule and must be like 4E+1 but not 4E+01, so, one cannot simply do printf("%lf", result);.

The solution of task’s author was the most comic code of all codes I’ve ever seen. And it works! I will preserve the original Russian comments and give some my English explanation.

//---------------------------------------------------------------------------

#include <vcl.h> /* Yep! We develop code in C++ Builder, so how could we live without Visial Component Library? */
#pragma hdrstop /* That's great that the C standard says that unknown pragmas must be ignored */

//---------------------------------------------------------------------------

#pragma argsused

#include <iostream.h> /* .h! Just to be compatible with Borland C++ :) */
#include <math.h>
#include<conio.h> /* Well, we must clean screen even if we work with files only */

int test(double (*p)[2],int i1,int c);          //Тестирование треугольника

/* `square' means `area'. BTW, we will use Heron's formula to calculate areas, not vector product! */
double square(double *p1,double *p2,double *p3);//Площадь по формуле Герона

/* How can we use Heron's formula without a function to calculate line segment's length? */
double len(double * p1, double * p2);           //Длина стороны

/*  We cannot trust math.h. Let's give the prototype here */
double round(double num);                       //Функция математического округления

const ndigit=5;

int main(int argc, char* argv[])
{
  double (*p)[2];
  int c /*количество вершин*/,i,j,ch;
  double buf;
  double s;        //Площадь многоугольника
  int direct;
  FILE * f_in,*f_out;
  f_in=fopen("z4.dat","r");
  f_out=fopen("z4.sol","w");
    /* The author will read input file twice */
    /* The first reading: let's summarize all newlines to calculate the number of vertices */
    //Сколько раз в файле f_in осуществлялся переход к новой строке?
    //Так как в первой строке указано направление обхода, а после
    //координат последней вершины нет перехода к новой строке,
    //то это значение равно количеству вершин многоугольника.
    //Итак, определяем количество вершин.
  c=0;
  while ((ch=fgetc(f_in))!=EOF)
    if (ch=='\n') c++;

  /* OK, we know the number of vertices. Let's rewind and read their coordinates */
  rewind(f_in);               //Переоткрываем файл f_in
  fscanf(f_in,"%d",&direct);  //direct - направление обхода

  /* That's why we need to know the number of vertices: we will keep them in an array! */
  p=new double [c][2];
  for (i=0;i<c;i++)
    fscanf(f_in,"%lf%lf",&p[i][0],&p[i][1]);

  /* pay attention to this cycle! */
  if (direct==1)              //Изменение направления обхода
    for(i=1,j=c-1;i<j;i++,j--)     {
       buf=p[i][0];
       p[i][0]=p[j][0];
       p[j][0]=buf;
       buf=p[i][1];
       p[i][1]=p[j][1];
       p[j][1]=buf;
     }
   s=0.0;
   /* Let the show begin! */
            //Начинаем вычислять площадь многоугольника
   while (c>2)       //Пока не останется 2 вершины
  {
    i=0;           //Всегда начинаем с самой первой вершины
         //Тестирование трех точек:
                   //Если  отрезки (i,i+1) и (i+1,i+2) не обеспечивают
                   //выпуклость области "слева" от них
                   //либо (в случае выпуклости) внутри треугольника
                   //(i,i+1)-(i+1,i+2)-(i+2,i) содержатся другие
                   //вершины многоугольника, то переходи к следующей вершине
    while( !test(p,i,c))
    {
       i++;
    }
    s+=square(p[i],p[i+1],p[i+2]); //Прибавляем площадь треугольника (i,i+1)-(i+1,i+2)-(i+2,i)
    /* Wow! We shift the array! The complexity is O(n^2) now instead of O(n) */
    for (j=i+2;j<c;j++) //Удаляем вершину с номером i
     {
       p[j-1][0]=p[j][0];
       p[j-1][1]=p[j][1];
     }
     c--;              //Уменьшаем количество вершин
     i=0;              //Опять начинаем с самой первой вершины
   }
   char string[20],ps[10];

  /* Let's convert the result to string according to our rules */
  int dec,  //Положение десятичной точки (0 - перед первой цифрой,
            //>0 - правее, <0 - левее
      sign; //Знак числа 0 - положительное, 1 - отрицательное число
            // ndigit - количество выделяемых в мантиссе цифр
  strcpy(string,ecvt(s,ndigit,&dec,&sign));
  s=round(s*pow(10,(5-dec)))/pow(10,(5-dec));
  strcpy(string,ecvt(s,ndigit,&dec,&sign));
  strncpy(&string[2],&string[1],strlen(string));
  string[1]='.';
  fprintf(f_out,"%s",strcat(strcat(string,(dec-1>=0?"E+":"E")),itoa(dec-1,ps,10)));
  fclose(f_out);
  fclose(f_in);
  return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s