Informatika gyűjtemény

Egy szinttel feljebb kb_vektorok.cs

2004050607080910

<<  5. óra - Kombináció  >>

<<  Vektorok  >>

NézetNyomtat

kb_vektorok.cs (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 2 KB
using System;
using System.IO;

namespace hu.krivan.szakkor.Vektorok
{
    struct Vector
    {
        public int x, y;
    }
    
    struct Point
    {
        public int x, y;
    }
    
    class VectorManager
    {
        public Vector[] vectors;
        public int n, k;
        
        public void chooseVectors()
        {
            // kombináció: nCk
            int[] a = new int[k+2];
            int[] minA = new int[0];
            for( int i=0; i<k; i++ ) a[i] = i;
            a[k] = n;
            a[k+1] = -1;
            
            // a = {0,1,2,3,...,k-1, k,-1}
            
            int j; // ezzel szaladgálunk
            long min = Int64.MaxValue;
            while( true )
            {
                long d = useChoosenVectors( a );
                if( d < min ) {
                    d = min;
                    minA = new int[k+2];
                    a.CopyTo(minA, 0); // elmenjtük minA-ban.
                }
                j = 0;
                while( a[j]+1 == a[j+1] )
                {
                    a[j] = j;
                    j++;
                }
                if( j==k ) break;
                a[j]++;
            }
            
            // kiírjuk a jó vektorokat -> amiből egybefüggő sokszög lesz.
            for( int i=0; i<k; i++ )
            {
                Console.Write("("+vectors[minA[i]].x+";"+vectors[minA[i]].y+")");
                if( i != k-1 ) Console.Write("+");
            }
            
            Console.ReadKey();
        }
        
        public long sqr( int a )
        {
            return a*a;
        }
        
        // használjuk a kiválasztott vektorokat
        public long useChoosenVectors( int[] a )
        {
            Point[] points = new Point[k];
            int x = 0;
            int y = 0;
            for( int i=0; i<k; i++ )
            {
                // összefűzés
                x += vectors[a[i]].x;
                y += vectors[a[i]].y;
                points[i].x = x;
                points[i].y = y; // elmentjük a pontokat
            }
            if( x == 0 && y == 0 ) {
                // van egy jó megoldásunk.
                // számoljunk egy legnagyobb átmérőt.
                long max = 0;
                long diameter = 0;
                for( int f=0; f<k; f++ )
                {
                    for( int g=f+1; g<k; g++ )
                    {
                        if( f == g ) continue;
                        // két pont közti távolság
                        diameter = sqr(points[f].x-points[g].x)+sqr(points[f].y-points[g].y);
                        if( diameter > max ) max = diameter; // maximális átmérő
                    }
                }
                return max;
            } else return Int64.MaxValue;
        }
        
        public void getVectors()
        {
            // fájlbeolvasás
            StreamReader sr = new StreamReader("vektor4.be");
            string[] firstLine = sr.ReadLine().Split(' ');
            n = Int32.Parse(firstLine[0]);
            k = Int32.Parse(firstLine[1]);
            
            vectors = new Vector[n];
            
            for( int i=0; i<n; i++ )
            {
                string[] coords = sr.ReadLine().Split(' ');
                vectors[i].x = Int32.Parse( coords[0] );
                vectors[i].y = Int32.Parse( coords[1] );
            }
        }
        
        public static void Main(string[] args)
        {
            VectorManager vm = new VectorManager();
            vm.getVectors(); // beolvasás
            vm.chooseVectors(); // üzleti logika
        }
    }
}
(Vissza)