Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- import java.util.Arrays.*;
- public class TargetLab {
- class Punto {
- private long ascissa;
- private long ordinata;
- public Punto (long ascissa, long ordinata) {
- this.ascissa = ascissa;
- this.ordinata = ordinata;
- }
- public long getAscissa() {
- return this.ascissa;
- }
- public long getOrdinata() {
- return this.ordinata;
- }
- public void setAscissa(long ascissa) {
- this.ascissa = ascissa;
- }
- public void setOrdinata(long ordinata) {
- this.ordinata = ordinata;
- }
- }
- class Poligono {
- private LinkedList<Punto> puntipoligono;
- public Poligono() {
- this.puntipoligono = new LinkedList<Punto>();
- }
- public LinkedList<Punto> getPuntiPoligono() {
- return this.puntipoligono;
- }
- }
- private Poligono poligonoCostruito;
- private LinkedList<Punto> PuntiDaVerificare;
- private int indexMin;
- private Punto puntoMin;
- public TargetLab () {
- this.PuntiDaVerificare = new LinkedList<Punto>();
- this.poligonoCostruito = new Poligono();
- }
- public void Acquisizione() throws IOException {
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- StringTokenizer st = new StringTokenizer(br.readLine());
- int n = Integer.parseInt(st.nextToken());
- String PuntoPoligono = br.readLine();
- StringTokenizer stt = new StringTokenizer(PuntoPoligono);
- long x = Long.parseLong(stt.nextToken());
- long y = Long.parseLong(stt.nextToken());
- Punto pp = new Punto (x,y);
- this.puntoMin = new Punto(x,y);
- this.indexMin = 0;
- this.poligonoCostruito.getPuntiPoligono().add(pp);
- for(int i = 1; i<=n-1; i++) {
- PuntoPoligono = br.readLine();
- stt = new StringTokenizer(PuntoPoligono);
- x = Long.parseLong(stt.nextToken());
- y = Long.parseLong(stt.nextToken());
- Punto p = new Punto (x,y);
- if(y<this.poligonoCostruito.puntipoligono.get(i-1).ordinata) {
- this.indexMin = i;
- this.puntoMin = p;
- }
- this.poligonoCostruito.getPuntiPoligono().add(p);
- }
- this.poligonoCostruito.puntipoligono.add(pp);
- st = new StringTokenizer(br.readLine());
- n = Integer.parseInt(st.nextToken());
- for(int i = 0; i<n; i++) {
- String PuntoDaVerificare = br.readLine();
- st = new StringTokenizer(PuntoDaVerificare);
- x = Long.parseLong(st.nextToken());
- y = Long.parseLong(st.nextToken());
- Punto p = new Punto (x,y);
- this.PuntiDaVerificare.add(p);
- }
- }
- public static long DetIt(long [][] mat) { //Assumendo che siano matrici di dimensione 3x3
- 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]);
- }
- public static int BinSearch(int[]a, int n, int inizio, int fine) {
- int centro = (int)(inizio+fine)/2;
- if(inizio > fine) {
- return -1;
- }
- else if(a[centro] == n) {
- return centro;
- }
- else if(a[centro]<n) {
- return BinSearch(a,n,centro+1,fine);
- }
- else {
- return BinSearch(a,n,inizio,centro-1);
- }
- }
- /**
- * @param args the command line arguments
- */
- public static LinkedList<Punto> BinSearchDecrPunto(LinkedList<Punto> l, long ordinata, int inizio, int fine, LinkedList<Punto> res) {
- int centro = (int)(inizio+fine)/2;
- if(inizio > fine) {
- res = new LinkedList<Punto>();
- res.add(l.get(inizio));
- res.add(l.get(fine));
- return res;
- }
- else if(l.get(centro).ordinata == ordinata) {
- res = new LinkedList<Punto>();
- res.add(l.get(centro-1));
- res.add(l.get(centro));
- return res;
- }
- else if(l.get(centro).ordinata<ordinata) {
- return BinSearchDecrPunto(l,ordinata,inizio, centro-1,res);
- }
- else {
- return BinSearchDecrPunto(l,ordinata,centro+1,fine,res);
- }
- }
- public static LinkedList<Punto> BinSearchCrPunto(LinkedList<Punto> l, long ordinata, int inizio, int fine, LinkedList<Punto> res) {
- int centro = (int)(inizio+fine)/2;
- if(inizio > fine) {
- res = new LinkedList<Punto>();
- res.add(l.get(fine));
- res.add(l.get(inizio));
- return res;
- }
- else if(l.get(centro).ordinata == ordinata) {
- res = new LinkedList<Punto>();
- res.add(l.get(centro));
- res.add(l.get(centro+1));
- return res;
- }
- else if(l.get(centro).ordinata<ordinata) {
- return BinSearchCrPunto(l,ordinata,centro+1,fine,res);
- }
- else {
- return BinSearchCrPunto(l,ordinata,inizio,centro-1,res);
- }
- }
- public boolean contenimento(Punto p) {
- if(p.ordinata>this.poligonoCostruito.puntipoligono.get(0).ordinata) {
- return false;
- }
- else if(p.ordinata<this.poligonoCostruito.puntipoligono.get(indexMin).ordinata) {
- return false;
- }
- else {
- LinkedList<Punto> sx = new LinkedList<Punto>();
- sx = BinSearchDecrPunto(this.poligonoCostruito.getPuntiPoligono(), p.ordinata, 0, this.indexMin, sx);
- if(sx.get(0).ordinata<sx.get(1).ordinata) {
- Punto pp = sx.get(0);
- sx.remove(0);
- sx.add(pp);
- }
- LinkedList<Punto> dx = new LinkedList<Punto>();
- dx = BinSearchCrPunto(this.poligonoCostruito.getPuntiPoligono(), p.ordinata, this.indexMin, this.poligonoCostruito.getPuntiPoligono().size()-1, dx);
- long[][] mat = new long[3][3];
- mat[0][0] = sx.get(0).ascissa;
- mat[0][1] = sx.get(0).ordinata;
- mat[0][2] = 1;
- mat[1][0] = sx.get(1).ascissa;
- mat[1][1] = sx.get(1).ordinata;
- mat[1][2] = 1;
- mat[2][0] = p.ascissa;
- mat[2][1] = p.ordinata;
- mat[2][2] = 1;
- System.out.println("Matrice1:");
- for(int i = 0; i<mat.length; i++) {
- for(int j = 0; j<mat.length; j++) {
- System.out.print(mat[i][j] + " ");
- }
- System.out.println();
- }
- long prima = DetIt(mat);
- System.out.println(prima);
- mat[0][0] = dx.get(0).ascissa;
- mat[0][1] = dx.get(0).ordinata;
- mat[0][2] = 1;
- mat[1][0] = dx.get(1).ascissa;
- mat[1][1] = dx.get(1).ordinata;
- mat[1][2] = 1;
- mat[2][0] = p.ascissa;
- mat[2][1] = p.ordinata;
- mat[2][2] = 1;
- System.out.println("Matrice2:");
- for(int i = 0; i<mat.length; i++) {
- for(int j = 0; j<mat.length; j++) {
- System.out.print(mat[i][j] + " ");
- }
- System.out.println();
- }
- long seconda = DetIt(mat);
- System.out.println(seconda);
- if(prima >= 0 && seconda >=0) {
- return true;
- }
- return false;
- }
- }
- /*public static boolean contenutoIn(Poligono po, Punto p) {
- for(int i = 0; i<po.puntipoligono.size()-1; i++) {
- long[][] mat = new long[3][3];
- mat[0][0] = po.getPuntiPoligono().get(i).ascissa;
- mat[0][1] = po.getPuntiPoligono().get(i).ordinata;
- mat[0][2] = 1;
- mat[1][0] = po.getPuntiPoligono().get(i+1).ascissa;
- mat[1][1] = po.getPuntiPoligono().get(i+1).ordinata;
- mat[1][2] = 1;
- mat[2][0] = p.ascissa;
- mat[2][1] = p.ordinata;
- mat[2][2] = 1;
- if(DetIt(mat)<0) {
- return false;
- }
- }
- return true;
- }
- */
- public static void main(String[] args) throws IOException {
- // TODO code application logic here
- TargetLab appo = new TargetLab();
- appo.Acquisizione();
- Date start=new Date();
- System.out.println("Start="+start);
- System.out.println("Punti del poligono: ");
- System.out.println(appo.poligonoCostruito.getPuntiPoligono().size());
- for(int i = 0; i<appo.poligonoCostruito.getPuntiPoligono().size(); i++) {
- Punto p = appo.poligonoCostruito.getPuntiPoligono().get(i);
- System.out.print("Ascissa: " + p.ascissa + " Ordinata: " + p.ordinata);
- System.out.println();
- }
- System.out.println("Punti da verificare: ");
- for(int i = 0; i<appo.PuntiDaVerificare.size(); i++) {
- Punto p = appo.PuntiDaVerificare.get(i);
- System.out.print("Ascissa: " + p.ascissa + " Ordinata: " + p.ordinata);
- System.out.println();
- }
- int indiceminimo = appo.indexMin;
- Punto p = appo.puntoMin;
- System.out.println("L'indice minimo è: " + indiceminimo + " e corrisponde al punto: " + p.ascissa + " " + p.ordinata);
- Punto pp = appo.PuntiDaVerificare.get(0);
- LinkedList<Punto> sx = new LinkedList<Punto>();
- LinkedList<Punto> dx = new LinkedList<Punto>();
- sx = BinSearchDecrPunto(appo.poligonoCostruito.getPuntiPoligono(),pp.ordinata,0,indiceminimo,sx);
- dx = BinSearchCrPunto(appo.poligonoCostruito.getPuntiPoligono(),pp.ordinata,indiceminimo,appo.poligonoCostruito.getPuntiPoligono().size()-1,dx);
- for(int i = 0; i<sx.size(); i++) {
- System.out.print("Punto è: " + sx.get(i).ascissa + " " + sx.get(i).ordinata);
- }
- for(int i = 0; i<dx.size(); i++) {
- System.out.print("Punto è: " + dx.get(i).ascissa + " " + dx.get(i).ordinata);
- }
- for(int j = 0; j<appo.PuntiDaVerificare.size(); j++) {
- System.out.println(appo.contenimento(appo.PuntiDaVerificare.get(j)));
- }
- /*int[][] mat = new int[3][3];
- System.out.println(DetIt(mat));
- mat[0][0] = 1;
- mat[0][1] = 3;
- mat[0][2] = 5;
- mat[1][0] = 0;
- mat[1][1] = 1;
- mat[1][2] = 1;
- mat[2][0] = 2;
- mat[2][1] = 1;
- mat[2][2] = 1;
- System.out.println(DetIt(mat));
- mat[0][0] = 0;
- mat[0][1] = 0;
- mat[0][2] = 1;
- mat[1][0] = 1;
- mat[1][1] = 0;
- mat[1][2] = 1;
- mat[2][0] = 2;
- mat[2][1] = 3;
- mat[2][2] = 0;
- System.out.println(DetIt(mat));
- int [][] m = new int [3][3];
- m[0][0] = -2;
- m[0][1] = 2;
- m[0][2] = -3;
- m[1][0] = -1;
- m[1][1] = 1;
- m[1][2] = 3;
- m[2][0] = 2;
- m[2][1] = 0;
- m[2][2] = -1;
- System.out.println(DetIt(m));
- System.out.println(calcolaDeterminante(m));
- int[] ar = new int[10];
- ar[0] = 1;
- ar[1] = 2;
- ar[2] = 3;
- ar[3] = 4;
- ar[4] = 5;
- ar[5] = 6;
- ar[6] = 7;
- ar[7] = 8;
- ar[8] = 9;
- ar[9] = 10;
- System.out.println(BinSearch(ar, 1, 0, 9));
- System.out.println(BinSearch(ar, 5, 0,9));
- System.out.println(BinSearch(ar, 24, 0, 9));
- int[] ar2 = new int [100];
- for(int i = 0; i<ar2.length; i++) {
- ar2[i] = i;
- }
- ar2[0] = 25;
- ar2[11] = 19;
- ar2[43] = 90;
- System.out.println(BinSearch(ar2,0,0,99));
- System.out.println(BinSearch(ar2,-10,0,99));
- System.out.println(BinSearch(ar2,25,0,99));
- System.out.println(BinSearch(ar2,19,0,99));
- System.out.println(BinSearch(ar2,90,0,99));
- }*/
- /*for(int j = 0; j<appo.PuntiDaVerificare.size(); j++) {
- System.out.println(contenutoIn(appo.poligonoCostruito, appo.PuntiDaVerificare.get(j)));
- }
- /*Date end=new Date();
- System.out.println("End="+end);
- float tempo=(end.getTime()-start.getTime())/1000;
- System.out.println("Totale="+tempo+" secondi");
- /*for( int i = 0; i < dotsList.length; i++ ){
- Dot a = dotsList[i];
- Dot b = dotsList[(i + 1)%dotsList.length];
- int sarrus = a.x*b.y + a.y*x + b.x*y - b.y*x - a.y*b.x - a.x*y;
- if(sarrus < 0){
- return false;
- }
- }
- return true;*/
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement