nuke.c

/*
https://dpaste.de/KTGe/raw

АО  «Котлин-Новатор»  является  крупным  разработчиком  и   производителем  бортовых комплексов,  вычислительных  систем,   процессоров  сигналов,  многофункциональных  РЛС,  систем электронной   индикации  тяжелых  транспортных  самолетов.
...
Условия работы:
- заработная плата от 35 т.р. для инженеров-программистов без опыта работы и от 50 т.р. с опытом работы;
- рабочий день с 8-15 до 16-45;
- оформление в соответствии с ТК РФ;
- коллективный отпуск в июле;
- работа в районе станции метро Площадь Александра Невского;
...
Задача для соискателей:

Вы  оператор  пуска  ракет  на  ядерном  подводном  ракетоносце.  В   результате  ядерного  удара противника  вы  потеряли  возможность   воспользоваться  большей  частью  боезапаса  и  системой автоматического  наведения. Всё,  что  у  вас  теперь  есть  -  файл  с  координатами   целей,  одна  боеспособная  ракета,  и компилятор C  на  единственном  уцелевшем ноутбуке. Вам  нужно  вычислить  оптимальные  координаты   точки,  куда  следует  произвести  запуск, чтобы причинить   максимальный  ущерб противнику.   Вам известна характеристика  боевой   части  вашей  ракеты  -  радиус  поражения.
Входные данные:
- Текстовый файл с координатами целей в декартовой системе координат,  каждая строка файла это пара целых чисел от 0 до 99, записанных через  запятую.
- Радиус  поражения  боевой  части  ракеты (целое число). Выходные данные:
- Координаты оптимальной точки, куда следует произвести запуск.
- Количество поражённых целей. Программа  должна  вызываться  из   командной  строки  с  двумя  параметрами  -  именем  файла с   координатами  и  радиусом поражения.

Вот  так:  nuke.exe coords.txt  10
*/

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

void test();

#define MAX_POINTS 10000

typedef struct {
    double x,y;
} point;

#define dist(p1,p2) (sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)))

int nuke(point * p, int points, int r, point * out)
{
    int coverage = 0;
    int i, j, k, t, count;
    point c;

    // for each pair of points: check 2 tangent circles, calc coverage
    for (i=0;i<points;i++) for (j=i+1;j<points;j++)
    {
        double d = dist(p[i], p[j]);
        if (d!=0 && d<=2*r)
        {
            double h = d/2;
            double m = sqrt(r*r - h*h);

            for (t=0;t<2;t++)
            {
                int sign = t ? 1 : -1;

                c.x = (p[i].x+p[j].x)/2 + m * (p[i].y-p[j].y)/d * sign;
                c.y = (p[i].y+p[j].y)/2 + m * (p[j].x-p[i].x)/d * sign;

                for (count=0, k=0; k<points; k++)
                    if (dist(c, p[k])<=r)
                        count++;

                if (count>coverage)
                {
                    coverage = count;
                    out->x = c.x;
                    out->y = c.y;
                }
            }
        }
        else if (coverage==0) // no tangent
            out->x = p[i].x, out->y = p[i].y;
    }

    return coverage;
}

int main(int argc, char ** argv)
{
    FILE * fp;
    int i, coverage;
    point c;
    point p[MAX_POINTS];
    char * fname = argc>1 ? argv[1] : "coords.txt";
    int r = argc>2 ? atoi(argv[2]) : 10;

    if (argc==1)
    {
        printf("No arguments, running test...\n");
        test();
        return 1;
    }

    fp = fopen (fname,"r");
    if (!fp)
        return 1;

    // load points
    for (i=0;fscanf(fp,"%lf,%lf",&p[i].x,&p[i].y)==2 && i<MAX_POINTS;i++);

    // nuke
    coverage = nuke(p, i, r, &c);

    // print results
    printf("%d,%d\n", (int)c.x, (int)c.y);
    printf("%d\n", coverage);

    fclose(fp);

    return 0;
}

/* tests =============================================================== */

int g_width = 100;
int g_height = 100;
int * g_data;
unsigned int g_color = 0xff00ff;

void DrawPixel(int x, int y)
{
    if (x>=0 && x<g_width && y>=0 && y<g_height)
        g_data[y*g_width+x] = g_color;
}

// https://en.wikipedia.org/wiki/Midpoint_circle_algorithm
void DrawCircle(int x0, int y0, int radius)
{
  int x = radius;
  int y = 0;
  int decisionOver2 = 1 - x;   // Decision criterion divided by 2 evaluated at x=r, y=0

  while( y <= x )
  {
    DrawPixel( x + x0,  y + y0);
    DrawPixel( y + x0,  x + y0);
    DrawPixel(-x + x0,  y + y0);
    DrawPixel(-y + x0,  x + y0);
    DrawPixel(-x + x0, -y + y0);
    DrawPixel(-y + x0, -x + y0);
    DrawPixel( x + x0, -y + y0);
    DrawPixel( y + x0, -x + y0);
    y++;
    if (decisionOver2<=0)
    {
      decisionOver2 += 2 * y + 1;   // Change in decision criterion for y -> y+1
    }
    else
    {
      x--;
      decisionOver2 += 2 * (y - x) + 1;   // Change for y -> y+1, x -> x-1
    }
  }
}

void saveTexture(char *filename, int w, int h, int *src)
{
    FILE *f;
    char buf[256];
    int i,x,y,c;
    unsigned char r, g, b, a;
    unsigned char bmpfileheader[14] = {'B','M', 0,0,0,0, 0,0, 0,0, 54,0,0,0};
    unsigned char bmpinfoheader[40] = {40,0,0,0, 0,0,0,0, 0,0,0,0, 1,0, 24,0};
    unsigned char bmppad[3] = {0,0,0};

    unsigned char *img;
    int filesize = 54 + 3*w*h;  //w is your image width, h is image height, both int
    img = (unsigned char *)malloc(3*w*h);
    memset(img,0,3*w*h);

    for(y=0; y<h; y++) for (x=0; x<w; x++)
    {
        c = src[(h - 1 - y) * w + x];
        a = (c >> 24) & 0xFF;
        r = (c >> 16) & 0xFF;
        g = (c >> 8) & 0xFF;
        b = c & 0xFF;
        img[(x+y*w)*3+2] = (unsigned char)(r);
        img[(x+y*w)*3+1] = (unsigned char)(g);
        img[(x+y*w)*3+0] = (unsigned char)(b);
    }

    bmpfileheader[ 2] = (unsigned char)(filesize);
    bmpfileheader[ 3] = (unsigned char)(filesize>>8);
    bmpfileheader[ 4] = (unsigned char)(filesize>>16);
    bmpfileheader[ 5] = (unsigned char)(filesize>>24);

    bmpinfoheader[ 4] = (unsigned char)(w);
    bmpinfoheader[ 5] = (unsigned char)(w>> 8);
    bmpinfoheader[ 6] = (unsigned char)(w>>16);
    bmpinfoheader[ 7] = (unsigned char)(w>>24);
    bmpinfoheader[ 8] = (unsigned char)(h);
    bmpinfoheader[ 9] = (unsigned char)(h>> 8);
    bmpinfoheader[10] = (unsigned char)(h>>16);
    bmpinfoheader[11] = (unsigned char)(h>>24);

    sprintf(buf, "%s.bmp", filename);
    f = fopen(buf,"wb");
    fwrite(bmpfileheader,1,14,f);
    fwrite(bmpinfoheader,1,40,f);
    for(i=0; i<h; i++)
    {
        fwrite(img+(w*(h-i-1)*3),3,w,f);
        fwrite(bmppad,1,(4-(w*3)%4)%4,f);
    }

    fclose(f);
    free(img);
}

int gen(point * p, int points, int w, int h)
{
    int i;
    for (i=0;i<points;i++)
        p[i].x = rand() % w, p[i].y = rand() % h;
    return points;
}

int draw(char * name, point * p, int points, int r, point c)
{
    int i;
    int size = g_width*g_height;
    g_data = (int*)malloc(size*sizeof(int));
    memset(g_data, 0xff, size*sizeof(int));

    g_color = 0xffff0000;
    DrawCircle((int)c.x, (int)c.y, r);

    g_color = 0xff000000;
    for (i=0;i<points;i++)
        DrawCircle(p[i].x, p[i].y, 5);

    saveTexture(name, g_width, g_height, g_data);

    free(g_data);
    return 0;
}

void test()
{
    point p[MAX_POINTS];
    point c;
    int i;
    int r = 128;
    int w = 512;
    int h = 512;
    int points = 15;

    time_t t;
    srand((unsigned) time(&t));

    g_width = w;
    g_height = h;

    for (i=0;i<50;i++)
    {
        char buf[256];
        sprintf(buf,"nuke_%04d", i);

        r = 32 + rand() % 64;

        gen(p, points, w, h);
        nuke(p, points, r, &c);
        draw(buf, p, points, r, c);
    }
}