Advertisement
Guest User

Untitled

a guest
Nov 25th, 2013
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 13.15 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3. import java.util.Arrays.*;
  4.  
  5.  
  6.  
  7. public class TargetLab {
  8.  
  9.     class Punto {
  10.         private long ascissa;
  11.         private long ordinata;
  12.        
  13.         public Punto (long ascissa, long ordinata) {
  14.             this.ascissa = ascissa;
  15.             this.ordinata = ordinata;
  16.         }
  17.        
  18.         public long getAscissa() {
  19.             return this.ascissa;
  20.         }
  21.        
  22.         public long getOrdinata() {
  23.             return this.ordinata;
  24.         }
  25.        
  26.         public void setAscissa(long ascissa) {
  27.             this.ascissa = ascissa;
  28.         }
  29.        
  30.         public void setOrdinata(long ordinata) {
  31.             this.ordinata = ordinata;
  32.         }
  33.     }
  34.    
  35.     class Poligono {
  36.         private LinkedList<Punto> puntipoligono;
  37.        
  38.         public Poligono() {
  39.             this.puntipoligono = new LinkedList<Punto>();
  40.         }
  41.        
  42.         public LinkedList<Punto> getPuntiPoligono() {
  43.             return this.puntipoligono;
  44.         }
  45.     }
  46.    
  47.     private Poligono poligonoCostruito;
  48.     private LinkedList<Punto> PuntiDaVerificare;
  49.     private int indexMin;
  50.     private Punto puntoMin;
  51.    
  52.     public TargetLab () {
  53.         this.PuntiDaVerificare = new LinkedList<Punto>();
  54.         this.poligonoCostruito = new Poligono();
  55.     }    
  56.    
  57.     public void Acquisizione() throws IOException {
  58.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  59.         StringTokenizer st = new StringTokenizer(br.readLine());
  60.         int n = Integer.parseInt(st.nextToken());
  61.             String PuntoPoligono = br.readLine();
  62.             StringTokenizer stt = new StringTokenizer(PuntoPoligono);
  63.             long x = Long.parseLong(stt.nextToken());
  64.             long y = Long.parseLong(stt.nextToken());
  65.             Punto pp = new Punto (x,y);
  66.             this.puntoMin = new Punto(x,y);
  67.             this.indexMin = 0;
  68.             this.poligonoCostruito.getPuntiPoligono().add(pp);
  69.         for(int i = 1; i<=n-1; i++) {
  70.             PuntoPoligono = br.readLine();
  71.             stt = new StringTokenizer(PuntoPoligono);
  72.             x = Long.parseLong(stt.nextToken());
  73.             y = Long.parseLong(stt.nextToken());
  74.             Punto p = new Punto (x,y);
  75.             if(y<this.poligonoCostruito.puntipoligono.get(i-1).ordinata) {
  76.                 this.indexMin = i;
  77.                 this.puntoMin = p;
  78.             }
  79.             this.poligonoCostruito.getPuntiPoligono().add(p);
  80.         }
  81.         this.poligonoCostruito.puntipoligono.add(pp);
  82.        
  83.         st = new StringTokenizer(br.readLine());
  84.         n = Integer.parseInt(st.nextToken());
  85.         for(int i = 0; i<n; i++) {
  86.             String PuntoDaVerificare = br.readLine();
  87.             st = new StringTokenizer(PuntoDaVerificare);
  88.             x = Long.parseLong(st.nextToken());
  89.             y = Long.parseLong(st.nextToken());
  90.             Punto p = new Punto (x,y);
  91.             this.PuntiDaVerificare.add(p);
  92.         }
  93.     }
  94.    
  95.  
  96.    
  97.     public static long DetIt(long [][] mat) { //Assumendo che siano matrici di dimensione 3x3
  98.         return mat[0][0]*(mat[1][1]*mat[2][2]-mat[2][1]*mat[1][2]) - mat[0][1]*(mat[1][0]*mat[2][2] - mat[2][0]*mat[1][2]) + mat[0][2]*(mat[1][0]*mat[2][1] - mat[2][0]*mat[1][1]);
  99.     }
  100.      
  101.    
  102.     public static int BinSearch(int[]a, int n, int inizio, int fine) {
  103.         int centro = (int)(inizio+fine)/2;
  104.         if(inizio > fine) {
  105.                     return -1;
  106.                 }
  107.                 else if(a[centro] == n) {
  108.                     return centro;
  109.                 }
  110.                 else if(a[centro]<n) {
  111.                     return BinSearch(a,n,centro+1,fine);
  112.                 }
  113.                 else {
  114.                     return BinSearch(a,n,inizio,centro-1);
  115.                 }
  116.     }          
  117.     /**
  118.      * @param args the command line arguments
  119.      */
  120.    
  121.  
  122.    
  123.     public static LinkedList<Punto> BinSearchDecrPunto(LinkedList<Punto> l, long ordinata, int inizio, int fine, LinkedList<Punto> res) {
  124.         int centro = (int)(inizio+fine)/2;
  125.         if(inizio > fine) {
  126.                     res = new LinkedList<Punto>();
  127.                     res.add(l.get(inizio));
  128.                     res.add(l.get(fine));
  129.                     return res;
  130.                 }
  131.                 else if(l.get(centro).ordinata == ordinata) {
  132.                     res = new LinkedList<Punto>();
  133.                     res.add(l.get(centro-1));
  134.                     res.add(l.get(centro));
  135.                     return res;
  136.                 }
  137.                 else if(l.get(centro).ordinata<ordinata) {
  138.                     return BinSearchDecrPunto(l,ordinata,inizio, centro-1,res);
  139.                 }
  140.                 else {
  141.                     return BinSearchDecrPunto(l,ordinata,centro+1,fine,res);
  142.                 }
  143.     }
  144.    
  145.     public static LinkedList<Punto> BinSearchCrPunto(LinkedList<Punto> l, long ordinata, int inizio, int fine, LinkedList<Punto> res) {
  146.         int centro = (int)(inizio+fine)/2;
  147.         if(inizio > fine) {
  148.                     res = new LinkedList<Punto>();
  149.                     res.add(l.get(fine));
  150.                     res.add(l.get(inizio));
  151.                     return res;
  152.                 }
  153.                 else if(l.get(centro).ordinata == ordinata) {
  154.                     res = new LinkedList<Punto>();
  155.                     res.add(l.get(centro));
  156.                     res.add(l.get(centro+1));
  157.                     return res;
  158.                 }
  159.                 else if(l.get(centro).ordinata<ordinata) {
  160.                     return BinSearchCrPunto(l,ordinata,centro+1,fine,res);
  161.                 }
  162.                 else {
  163.                     return BinSearchCrPunto(l,ordinata,inizio,centro-1,res);
  164.                 }
  165.     }
  166.    
  167.     public boolean contenimento(Punto p) {
  168.         if(p.ordinata>this.poligonoCostruito.puntipoligono.get(0).ordinata) {
  169.             return false;
  170.         }
  171.         else if(p.ordinata<this.poligonoCostruito.puntipoligono.get(indexMin).ordinata) {
  172.             return false;
  173.         }
  174.         else {
  175.             LinkedList<Punto> sx = new LinkedList<Punto>();
  176.             sx = BinSearchDecrPunto(this.poligonoCostruito.getPuntiPoligono(), p.ordinata, 0, this.indexMin, sx);
  177.             if(sx.get(0).ordinata<sx.get(1).ordinata) {
  178.                 Punto pp = sx.get(0);
  179.                 sx.remove(0);
  180.                 sx.add(pp);
  181.             }
  182.            
  183.             LinkedList<Punto> dx = new LinkedList<Punto>();
  184.             dx = BinSearchCrPunto(this.poligonoCostruito.getPuntiPoligono(), p.ordinata, this.indexMin, this.poligonoCostruito.getPuntiPoligono().size()-1, dx);
  185.        
  186.         long[][] mat = new long[3][3];
  187.         mat[0][0] = sx.get(0).ascissa;
  188.         mat[0][1] = sx.get(0).ordinata;
  189.         mat[0][2] = 1;
  190.         mat[1][0] = sx.get(1).ascissa;
  191.         mat[1][1] = sx.get(1).ordinata;
  192.         mat[1][2] = 1;
  193.         mat[2][0] = p.ascissa;
  194.         mat[2][1] = p.ordinata;
  195.         mat[2][2] = 1;
  196.         System.out.println("Matrice1:");
  197.         for(int i = 0; i<mat.length; i++) {
  198.             for(int j = 0; j<mat.length; j++) {
  199.                 System.out.print(mat[i][j] + " ");
  200.             }
  201.             System.out.println();
  202.         }
  203.         long prima = DetIt(mat);
  204.         System.out.println(prima);
  205.         mat[0][0] = dx.get(0).ascissa;
  206.         mat[0][1] = dx.get(0).ordinata;
  207.         mat[0][2] = 1;
  208.         mat[1][0] = dx.get(1).ascissa;
  209.         mat[1][1] = dx.get(1).ordinata;
  210.         mat[1][2] = 1;
  211.         mat[2][0] = p.ascissa;
  212.         mat[2][1] = p.ordinata;
  213.         mat[2][2] = 1;
  214.         System.out.println("Matrice2:");
  215.         for(int i = 0; i<mat.length; i++) {
  216.             for(int j = 0; j<mat.length; j++) {
  217.                 System.out.print(mat[i][j] + " ");
  218.             }
  219.             System.out.println();
  220.         }
  221.         long seconda = DetIt(mat);
  222.         System.out.println(seconda);
  223.         if(prima >= 0 && seconda >=0) {
  224.             return true;
  225.         }
  226.         return false;
  227.     }
  228.    
  229.     }
  230.    
  231.    
  232.     /*public static boolean contenutoIn(Poligono po, Punto p) {
  233.         for(int i = 0; i<po.puntipoligono.size()-1; i++) {
  234.             long[][] mat = new long[3][3];
  235.             mat[0][0] = po.getPuntiPoligono().get(i).ascissa;
  236.             mat[0][1] = po.getPuntiPoligono().get(i).ordinata;
  237.             mat[0][2] = 1;
  238.             mat[1][0] = po.getPuntiPoligono().get(i+1).ascissa;
  239.             mat[1][1] = po.getPuntiPoligono().get(i+1).ordinata;
  240.             mat[1][2] = 1;
  241.             mat[2][0] = p.ascissa;
  242.             mat[2][1] = p.ordinata;
  243.             mat[2][2] = 1;
  244.             if(DetIt(mat)<0) {
  245.                 return false;
  246.             }
  247.            
  248.         }
  249.         return true;
  250.     }
  251.    
  252.    
  253.    
  254.     */
  255.    
  256.     public static void main(String[] args) throws IOException {
  257.         // TODO code application logic here
  258.         TargetLab appo = new TargetLab();
  259.         appo.Acquisizione();
  260.         Date start=new Date();
  261.         System.out.println("Start="+start);
  262.         System.out.println("Punti del poligono: ");
  263.         System.out.println(appo.poligonoCostruito.getPuntiPoligono().size());
  264.         for(int i = 0; i<appo.poligonoCostruito.getPuntiPoligono().size(); i++) {
  265.             Punto p = appo.poligonoCostruito.getPuntiPoligono().get(i);
  266.             System.out.print("Ascissa: " + p.ascissa + " Ordinata: " + p.ordinata);
  267.             System.out.println();
  268.         }
  269.         System.out.println("Punti da verificare: ");
  270.         for(int i = 0; i<appo.PuntiDaVerificare.size(); i++) {
  271.             Punto p = appo.PuntiDaVerificare.get(i);
  272.             System.out.print("Ascissa: " + p.ascissa + " Ordinata: " + p.ordinata);
  273.             System.out.println();
  274.         }
  275.         int indiceminimo = appo.indexMin;
  276.         Punto p = appo.puntoMin;
  277.         System.out.println("L'indice minimo è: " + indiceminimo + " e corrisponde al punto: " + p.ascissa + " " + p.ordinata);
  278.         Punto pp = appo.PuntiDaVerificare.get(0);
  279.         LinkedList<Punto> sx = new LinkedList<Punto>();
  280.         LinkedList<Punto> dx = new LinkedList<Punto>();
  281.         sx = BinSearchDecrPunto(appo.poligonoCostruito.getPuntiPoligono(),pp.ordinata,0,indiceminimo,sx);
  282.         dx = BinSearchCrPunto(appo.poligonoCostruito.getPuntiPoligono(),pp.ordinata,indiceminimo,appo.poligonoCostruito.getPuntiPoligono().size()-1,dx);
  283.         for(int i = 0; i<sx.size(); i++) {
  284.             System.out.print("Punto è: " + sx.get(i).ascissa + " " + sx.get(i).ordinata);
  285.         }
  286.         for(int i = 0; i<dx.size(); i++) {
  287.             System.out.print("Punto è: " + dx.get(i).ascissa + " " + dx.get(i).ordinata);
  288.         }
  289.         for(int j = 0; j<appo.PuntiDaVerificare.size(); j++) {
  290.             System.out.println(appo.contenimento(appo.PuntiDaVerificare.get(j)));
  291.         }
  292.                 /*int[][] mat = new int[3][3];
  293.         System.out.println(DetIt(mat));
  294.         mat[0][0] = 1;
  295.         mat[0][1] = 3;
  296.         mat[0][2] = 5;
  297.         mat[1][0] = 0;
  298.         mat[1][1] = 1;
  299.         mat[1][2] = 1;
  300.         mat[2][0] = 2;
  301.         mat[2][1] = 1;
  302.         mat[2][2] = 1;
  303.         System.out.println(DetIt(mat));
  304.         mat[0][0] = 0;
  305.         mat[0][1] = 0;
  306.         mat[0][2] = 1;
  307.         mat[1][0] = 1;
  308.         mat[1][1] = 0;
  309.         mat[1][2] = 1;
  310.         mat[2][0] = 2;
  311.         mat[2][1] = 3;
  312.         mat[2][2] = 0;
  313.         System.out.println(DetIt(mat));
  314.         int [][] m = new int [3][3];
  315.         m[0][0] = -2;
  316.         m[0][1] = 2;
  317.         m[0][2] = -3;
  318.         m[1][0] = -1;
  319.         m[1][1] = 1;
  320.         m[1][2] = 3;
  321.         m[2][0] = 2;
  322.         m[2][1] = 0;
  323.         m[2][2] = -1;
  324.         System.out.println(DetIt(m));
  325.         System.out.println(calcolaDeterminante(m));
  326.        
  327.        
  328.         int[] ar = new int[10];
  329.         ar[0] = 1;
  330.         ar[1] = 2;
  331.         ar[2] = 3;
  332.         ar[3] = 4;
  333.         ar[4] = 5;
  334.         ar[5] = 6;
  335.         ar[6] = 7;
  336.         ar[7] = 8;
  337.         ar[8] = 9;
  338.         ar[9] = 10;
  339.         System.out.println(BinSearch(ar, 1, 0, 9));
  340.         System.out.println(BinSearch(ar, 5, 0,9));
  341.         System.out.println(BinSearch(ar, 24, 0, 9));
  342.         int[] ar2 = new int [100];
  343.         for(int i = 0; i<ar2.length; i++) {
  344.             ar2[i] = i;
  345.         }
  346.         ar2[0] = 25;
  347.         ar2[11] = 19;
  348.         ar2[43] = 90;
  349.         System.out.println(BinSearch(ar2,0,0,99));
  350.         System.out.println(BinSearch(ar2,-10,0,99));
  351.         System.out.println(BinSearch(ar2,25,0,99));
  352.         System.out.println(BinSearch(ar2,19,0,99));
  353.         System.out.println(BinSearch(ar2,90,0,99));
  354.     }*/
  355.         /*for(int j = 0; j<appo.PuntiDaVerificare.size(); j++) {
  356.             System.out.println(contenutoIn(appo.poligonoCostruito, appo.PuntiDaVerificare.get(j)));
  357.            
  358.        
  359.         }
  360.         /*Date end=new Date();
  361.                 System.out.println("End="+end);
  362.                         float tempo=(end.getTime()-start.getTime())/1000;
  363.                         System.out.println("Totale="+tempo+" secondi");
  364.         /*for( int i = 0; i < dotsList.length; i++ ){
  365.             Dot a = dotsList[i];
  366.             Dot b = dotsList[(i + 1)%dotsList.length];
  367.             int sarrus = a.x*b.y + a.y*x + b.x*y - b.y*x - a.y*b.x - a.x*y;
  368.             if(sarrus < 0){
  369.                 return false;
  370.             }
  371.         }
  372.         return true;*/
  373.     }
  374. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement