pdp forum

Κώδικας: Επιλογή όλων

/*
LANG: C++
TASK: evripos
*/
#include <iostream>
#include <fstream>
#include <cmath>
#define BIG 9007199254740991.0
using namespace std;

struct Point
{
   int x,y;
};
int N;
Point p[205];
double sol[205][205];
int n;
void quicksort (int l,int r)
{
     int i=l,j=r;
     Point m=p[(l+r)/2];
     
     while (i<=j)
     {
        while (i<=j && p[i].x<m.x) ++i;
        while (i<=j && p[j].x>m.x) --j;
        
        if (i<=j)
        {
            Point x=p[i];
            p[i]=p[j];
            p[j]=x;
            ++i;
            --j;
        }
     }
     
     if (l<j) quicksort(l,j);
     if (i<r) quicksort(i,r);
}
     

int main ()
{
    ifstream fin ("evripos.in");
    fin >> N;
    p[1].x=p[1].y=0;
    fin >> p[N+2].x >> p[N+2].y;
    for (int i=2;i<=N+1;++i)
    fin >> p[i].x >> p[i].y;
    fin.close();
    
    quicksort(1,N+2);
    
    sol[1][1]=0;
    sol[2][1]=sqrt((p[1].x-p[2].x)*(p[1].x-p[2].x)+(p[1].y-p[2].y)*(p[1].y-p[2].y));
    
    for (int i=3;i<=N+2;++i)
    for (int j=1;j<=i;++j)
    {
        if (i==j && i!=N+2)
        continue;
        
        if (i>j+1)
        {
            sol[i][j]=sol[i-1][j]+sqrt((p[i].x-p[i-1].x)*(p[i].x-p[i-1].x)+(p[i].y-p[i-1].y)*(p[i].y-p[i-1].y));
            ++n;
            continue;
        }
       
        double MIN=BIG;
        for (int k=1;k<j;++k)
        {
           ++n;
           double cost=sol[j][k]+sqrt((p[k].x-p[i].x)*(p[k].x-p[i].x)+(p[k].y-p[i].y)*(p[k].y-p[i].y));
           if (MIN>cost)
           MIN=cost;
        }
        sol[i][j]=MIN;
    }
    
    ofstream fout ("evripos.out");
    fout << round(sol[N+2][N+2]) << endl;
    fout << n << endl;
    return 0;
}

Κώδικας: Επιλογή όλων

chiossif@chiossif-6400:~/Code/PDP_21B/PDP_21_B_GYM$ cat gym.c
#include <stdio.h>
#include <stdlib.h>

int inline int_sqr(int x) {
    return x*x;
}

int main(void) {
    int *x, *y, *z, d, a, b, s1, s2, s3, s, n, n_1;
    register int i, j;

    scanf("%d",&n);
    n_1=n-1;
    x=malloc(n*sizeof(int));
    y=malloc(n*sizeof(int));
    z=malloc(n*sizeof(int));
    for (i=0;i<n;i++)
        scanf("%d %d %d", &x[i], &y[i],&z[i]);

    d=int_sqr(x[1]-x[0])+int_sqr(y[1]-y[0])+int_sqr(z[1]-z[0]);
    a=0;
    b=1;
    for (i=0;i<n_1;i++)
        for (j=i+1;j<n;j++)
            if ((s1=int_sqr(x[j]-x[i]))<=d &&
                (s2=int_sqr(y[j]-y[i]))<=d &&
                (s3=int_sqr(z[j]-z[i]))<=d && (s=s1+s2+s3)<d) {
                a=i;
                b=j;
                d=s;
            }
    printf("%d %d\n",a+1,b+1);

    return 0;
}
chiossif@chiossif-6400:~/Code/PDP_21B/PDP_21_B_GYM$ time ./gym <gym_10000.in
5540 8477

real	0m0.557s
user	0m0.528s
sys	0m0.004s
chiossif@chiossif-6400:~/Code/PDP_21B/PDP_21_B_GYM$ 

Κώδικας: Επιλογή όλων

PROGRAM evripos;

  {LANG: Pascal
   TASK: evripos}

  USES
      SysUtils;

  CONST
       MaxPoints = 204;
       INF =    100000;
  TYPE
       coordinates = record
              X:integer;
              Y:integer;
       end;
       Coordsys = array[1..MaxPoints] of coordinates;

  VAR
     N,
     I,J,K,
     d:integer;
     q:real;
     input,output:text;
     points:Coordsys;
     l:array[1..MaxPoints,1..MaxPoints] of real;

  FUNCTION dist(a,b:coordinates):real;   //euclidean distiance//
      BEGIN
        dist:=sqrt(sqr(a.X-b.X)+sqr(a.Y-b.Y))
      END;

  (*---------------- start of quicksort ------------------*)
  PROCEDURE swap(VAR a, b: coordinates);
      VAR
          t: integer;
      BEGIN
          t   := a.X;
          a.X := b.X;
          b.X := t;
          t   := a.Y;
          a.Y := b.Y;
          b.Y := t;
      END;

  FUNCTION Split(start, stop: integer): integer;
      VAR
          left, right: integer;
          pivot: integer;

      BEGIN
            pivot := points[start].X;
            left := start + 1;
            right := stop;
            WHILE left <= right DO BEGIN
                  WHILE (left <= stop) AND (points[left].X < pivot) DO
                        left := left + 1;
                  WHILE (right > start) AND (points[right].X >= pivot) DO
                        right := right - 1;
                  IF left < right THEN
                     swap(points[left], points[right]);
                  END;
            swap(points[start], points[right]);
            Split := right
      END;

  PROCEDURE QuicksortRecur(start, stop: integer);
            VAR
                splitpt: integer;

            BEGIN
                IF start < stop THEN BEGIN
                    splitpt := Split(start, stop);
                    QuicksortRecur(start, splitpt-1);
                    QuicksortRecur(splitpt+1, stop);
                END
            END;

  PROCEDURE Quicksort(size: Integer; VAR points: Coordsys);
        BEGIN
            QuicksortRecur(1, size)
        END;

  (*------------- end of quicksort ------------------*)

  BEGIN
  (*-------------    input data   -------------------*)
      assign(input,'evripos.in');
      reset(input);
      readln(input,N);
      N:=N+2;
      points[1].X:=0;
      points[1].Y:=0;
      readln(input,points[N].X,points[N].Y);
      FOR I := 2 TO N-1 DO
         readln(input,points[I].X,points[I].Y);
      close(input);
  (*--------------- end of input ---------------------*)

  (*-------- sorting coordinates by increasing X -----*)
      Quicksort(N, points);
  (*--------------------------------------------------*)


  (*--- computing all minimum normal bitonic paths ---*)

      FOR J := 2 TO N DO
          FOR I := 1 TO J-1 DO
            IF (I=1) AND (J=2) THEN
              l[I,J] := dist(points[i],points[j])
            ELSE IF J>I+1 THEN
                    l[I,J]:= l[I,J-1] + dist(points[J-1],points[J])
                 ELSE  BEGIN
                       l[I,J] := INF;
                       FOR K := 1 TO I-1 DO BEGIN
                          q:= l[K,I] + dist(points[K],points[J]);
                          IF q < l[I,J] THEN
                             l[I,J]:= q;
                          END;
                       END;

    (*------------------------------------------------*)

    (*----- computing the shortest bitonic tour ------*)
      d:= Round( l[n-1,n] + dist(points[n-1],points[n]));
    (*------------------------------------------------*)


    (*---------------- output data -------------------*)
      assign(output,'evripos.out');
      rewrite(output);
      writeln(output,d);
      close(output);
    (*--------------- end of output ------------------*)

end.

Κώδικας: Επιλογή όλων

program evripos;

type CoordSet = record
  x, y: Integer
end;

var Fi: TextFile;
    i, j, tmp, N: Integer;
    ans, dist: Array [1..203, 1..203] of Real;
    Coord: Array [1..203] of CoordSet;

begin
  Assign(Fi, 'evripos.in');
  Reset(Fi);
  ReadLn(Fi, N);
  ReadLn(Fi, Coord[N+1].x, Coord[N+1].y);
  for i:=1 to N do
    ReadLn(Fi, Coord[i].x, Coord[i].y);
  Close(Fi);
  
  N := N+2;  
  Coord[N].x := 0;
  Coord[N].y := 0;
  
  for i:=1 to N do
    for j:=1 to N do
      if Coord[i].x > Coord[j].x then begin
        tmp := Coord[i].x;
        Coord[i].x := Coord[j].x;
        Coord[j].x := tmp;
        tmp := Coord[i].y;
        Coord[i].y := Coord[j].y;
        Coord[j].y := tmp;
      end;
      
  for i:=1 to N do
    for j:=1 to N do begin
      dist[i, j] := sqrt( (Coord[i].x-Coord[j].x)*(Coord[i].x-Coord[j].x) + (Coord[i].y-Coord[j].y)*(Coord[i].y-Coord[j].y) );     
      ans[i, j] := 99999999;
    end;
  
  ans[1, 1] := 0;
  
  for i:=1 to N do
    for j:=1 to N do begin
      if ans[i+1, i] > ans[i, j]+dist[j, i+1] then
        ans[i+1, i] := ans[i, j]+dist[j, i+1];      
      if ans[i+1, j] > ans[i, j]+dist[i, i+1] then
        ans[i+1, j] := ans[i, j]+dist[i, i+1];            
      if ans[i+1, i+1] > ans[i, j]+dist[i, i+1]+dist[j, i+1] then
        ans[i+1, i+1] := ans[i, j]+dist[i, i+1]+dist[j, i+1];
    end;

  Assign(Fi, 'evripos.out');
  Rewrite(Fi);
  WriteLn(Fi, Round(ans[N, N]));
  Close(Fi);

  Halt(0);
end.