Informatika gyűjtemény

NézetNyomtat

kb_madar.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: 5 KB
// NEM TESZTELT MEGOLDÁS!!!
// de az alap tesztesetre működik.

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace Madar
{
    
    class Set<E> : IEnumerable
    {
        private List<E> list;

        public void Add( E item )
        {
            int index = list.BinarySearch(item);
            if (index < 0)
            {
                list.Insert(~index, item);
            }
        }

        public void AddAll( List<E> items )
        {
            foreach( E item in items )
            {
                Add( item );
            }
        }

        public Set()
        {
            list = new List<E>();
        }

        public Set( int capacity )
        {
            list = new List<E>(capacity);
        }

        public int Count {
            get {
                return list.Count;
            }
        }

        #region IEnumerable implementation
        
        public IEnumerator GetEnumerator ()
        {
            return list.GetEnumerator();
        }
        
        #endregion
        
    }
    
    class Position : IComparable<Position>
    {
        public int v; // ide dobáljuk az x1/x2/y1/y2-ket.
        public int idx; // a madár indexe
        public int type; // pontosan melyiket (1/2), az x/y-t, nem itt tároljuk.
        
        #region IComparable[Madar.Position] implementation
        
        public int CompareTo (Position other)
        {
            return v.CompareTo(other.v);
        }
        
        #endregion

        public Position( int v, int idx, int type )
        {
            this.v = v;
            this.idx = idx;
            this.type = type;
        }
    }
    
    class Bird
    {
        public int x1, y1, x2, y2;
        public Set<int> opponents = new Set<int>();
        
        public Bird( int y, int x, int radius, int size )
        {
            x1 = x-radius-1;
            if( x1 < 0 ) x1 = 0;
            y1 = y-radius-1;
            if( y1 < 0 ) y1 = 0;
            x2 = x+radius-1;
            if( x2 >= size ) x2 = size-1;
            y2 = y+radius-1;
            if( y2 >= size ) y2 = size-1;
        }
    }
    
    class Program
    {

        private int n, size;
        private List<Bird> birds;
        
        public Program()
        {
            // beolvassuk és egyben tömörítünk is
            GetTerritories();
            string AandB = SolveAandB();
            string C = SolveC();

            StreamWriter outs = new StreamWriter("madar.ki");
            outs.Write(AandB); // itt már van sorvége!
            outs.WriteLine(C);
            outs.Close();
        }

        public string SolveAandB()
        {
            // mi kell ehhez? egy tömb amibe "kipakolunk".
            // pakolás közben derül ki, hogy melyik madár kivel veszekszik, stb.
            Set<int>[,] land = new Set<int>[size,size];
            // a madark indexét fogjuk bepakolgatni.

            for( int i=0; i<birds.Count; i++ ) {
                for(int x = birds[i].x1; x <= birds[i].x2; x++) {
                    for(int y = birds[i].y1; y <= birds[i].y2; y++) {
                        if( land[x, y] == null ) {
                            land[x, y] = new Set<int>(n);
                            land[x, y].Add(i);
                        } else {
                            // megnézzük, hogy ki van itten és mindegyiknek beállítjuk ellenfélnek oda-vissza
                            foreach( int item in land[x, y] )
                            {
                                birds[item].opponents.Add( i );
                                birds[i].opponents.Add( item );
                            }
                            land[x, y].Add( i ); // végül hozzáadjuk a listához
                        }
                    }
                }
            }

            List<int> solo = new List<int>(n);
            int maxOpponent = 0, idx = -1;
            for( int i=0; i<birds.Count; i++ )
            {
                if( birds[i].opponents.Count == 0 ) solo.Add( i+1 ); else {
                    if( maxOpponent < birds[i].opponents.Count ) {
                        maxOpponent = birds[i].opponents.Count;
                        idx = i;
                    }
                }
            }

            StringBuilder sb = new StringBuilder();
            if( solo.Count == 0 ) {
                sb.AppendLine();
            } else {
                for( int i=0; i<solo.Count; i++ )
                    sb.Append(solo[i] + " ");
                sb.AppendLine();
            }

            if( idx == -1 ) {
                sb.AppendLine();
            } else {
                sb.AppendLine(""+(idx+1));
            }

            return sb.ToString();
        }

        public string SolveC()
        {
            // mindenkit mindekivel egyeztetünk.
            int sum = 0;
            for( int a=0; a<birds.Count; a++ ) {
                for( int b=a+1; b<birds.Count; b++ ) {
                    if(( birds[a].x1 >= birds[b].x1 && birds[a].x2 <= birds[b].x2 &&                        
                        birds[a].y1 >= birds[b].y1 && birds[a].y2 <= birds[b].y2) ||
                       ( birds[b].x1 >= birds[a].x1 && birds[b].x2 <= birds[a].x2 &&
                        birds[b].y1 >= birds[a].y1 && birds[b].y2 <= birds[a].y2)
                       ){
                        // ha valamelyik benne van a másikban akkor ++
                        sum++;
                    }
                }
            }
            
            return ""+sum;
        }
        
        public void GetTerritories()
        {
            StreamReader ins = new StreamReader("madar.be");
            string[] line = ins.ReadLine().Split(' ');

            n = int.Parse(line[0]);
            size = int.Parse(line[1]);

            birds = new List<Bird>(n);
            for( int i=0; i<n; i++ ) {
                line = ins.ReadLine().Split(' ');

                birds.Add( new Bird( int.Parse(line[0]), int.Parse(line[1]), int.Parse(line[2]), size ) );
            }

            // most a cél az lenne, hogy tömörítsünk, ehhez kicuccoljuk a madárkák x1 és x2-jét egy tömbbe.
            List<Position> positions = new List<Position>(2*n);
            Bird b;
            for( int i=0; i<birds.Count; i++ ) {
                b = birds[i];
                positions.Add( new Position( b.x1, i, 1 ) );
                positions.Add( new Position( b.x2, i, 2 ) );
            }

            positions.Sort();

            int prevPos = positions[0].v;
            int newPos = 0;
            for( int i=0; i<positions.Count; i++ ) {
                if( positions[i].v > prevPos ) {
                    newPos++;
                    prevPos = positions[i].v;
                }
                if( positions[i].type == 1 ) {
                    birds[ positions[i].idx ].x1 = newPos;
                } else {
                    birds[ positions[i].idx ].x2 = newPos;
                }               
            }

            int biggestPos = newPos;
                        
            positions.Clear();
            for( int i=0; i<birds.Count; i++ ) {
                b = birds[i];
                positions.Add( new Position( b.y1, i, 1 ) );
                positions.Add( new Position( b.y2, i, 2 ) );
            }

            positions.Sort();

            prevPos = positions[0].v;
            newPos = 0;
            for( int i=0; i<positions.Count; i++ ) {
                if( positions[i].v > prevPos ) {
                    newPos++;
                    prevPos = positions[i].v;
                }
                if( positions[i].type == 1 ) {
                    birds[ positions[i].idx ].y1 = newPos;
                } else {
                    birds[ positions[i].idx ].y2 = newPos;
                }               
            }

            if( biggestPos < newPos )
                biggestPos = newPos;
            
            size = biggestPos+1; // felülírjuk a méretet, hiszen mostmár ez az új méret.
        }
        
        public static void Main(string[] args)
        {
            new Program();
        }
    }
}
(Vissza)