Matematični forum I. gimnazije v Celju

Objavljeno: **Če Maj 18, 2017 11:47 am**

Na vrtu raste N čudovitih cvetlic, ki se nahajajo na koordinatah

(c^{(i)}_{x},c^{(i)}_{y}). Skrbni vrtnar Saša je namestil namakalni sistem, ki ima M šob za vodo. Posamezna šoba se nahaja na koordinatah

(s^{(i)}_{x},s^{(i)}_{y}) in zaliva cvetlice, ki od nje niso oddaljene več kot

r_i enot. Šobe lahko tudi sovpadajo s cvetlicami. Cvetlice so zelo odporne na prekomerno zalivanje, slabo pa prenašajo sušo.

Napišite program, ki bo učinkovito izračunal, koliko cvetlic je še vedno potrebno zalivati ročno, ker jih namakalni sistem ne doseže.

Vhodni podatki
Vsa števila v vhodnih podatkih so cela. V prvi vrstici se nahajata števili N in M. V naslednjih N vrsticah so podane koordinate cvetlic

c^{(i)}_{x} in

c^{(i)}_{y}. Nato sledi še M vrstic, ki opisujejo šobe namakalnega sistem s števili

s^{(i)}_{x},

s^{(i)}_{y} in

r_i. Koordinate po absolutni vrednosti ne presežejo 109.

Omejitve vhodnih podatkov

1≤N≤10^6
1≤M≤3000
1≤r_i≤1000
|c^{(i)}_{x}|≤10^9, |c^{(i)}_{y}|≤10^9, |s^{(i)}_{x}|≤10^9, |s^{(i)}_{y}|≤10^9

Izhodni podatki
Izpišite, koliko cvetlic namakalni sistem ne doseže.

Primer vhoda

Koda: Izberi vse

Pripadajoč izhod

Koda: Izberi vse

6

Objavljeno: **Po Jun 19, 2017 3:29 pm**

Koda: Izberi vse

import java.util.*;

public class Zalivanje
{
   public static void main(String[]args)
   {
      Scanner skan = new Scanner(System.in);
      int n = skan.nextInt();
      int m = skan.nextInt();

      List<int[]> roze = new ArrayList<int[]>();
      List<int[]> sobe = new ArrayList<int[]>();

      for(int i = 0; i < n; i++)
      {
         int[] roza = new int[2];
         roza[0] = skan.nextInt();
         roza[1] = skan.nextInt();
         roze.add(roza);
      }

      for(int i = 0; i < m; i++)
      {
         int[] soba = new int[3];
         soba[0] = skan.nextInt();
         soba[1] = skan.nextInt();
         soba[2] = skan.nextInt();
         sobe.add(soba);
      }

      for(int i = 0; i < m; i++)
      {
         int r = sobe.get(i)[2];
         int x1 = sobe.get(i)[0];
         int y1 = sobe.get(i)[1];

         for(int j = 0; j < roze.size(); j++)
         {
            int x2 = roze.get(j)[0];
            int y2 = roze.get(j)[1];
            double distance = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

            if(distance <= r)
            {
               roze.remove(j);
               j--;
            }   
         }   
      }

      System.out.println(roze.size());   
   }
}

Matematični forum I. gimnazije v Celju

Zalivanje

Zalivanje

Re: Zalivanje