Apostila MaratonaTo do List

-> Apostilar fórmulas geométricas = CELSO-> Apostilar métodos de otimização = CELSO-> Apostilar Grafos-> Apostilar Algoritmos Básicos

Abaixo, métodos em Java para resolver subproblemas importantes e reincidentes na Maratona de Programação.

Template //Não alterar

Entrada:

Saída:

Código:

Selection Sort//Não alterar

Entrada:

Saída:

Código:public static void SelectionSort(int[] v) {   int index_min,

  aux;

   for (int i=0; i<v.length; i++) {   index_min = i;   for (int j=i+1; j<v.length; j++) {      if (v[j]<v[index_min]) {         index_min=j;      }   }   if(index_min != i){     aux = v[index_min];     v[index_min] = v[i];     v[i] = aux;   }

   }}

QuickSort

Entrada:

Saída:

Código:public class QuickSort<E extends Comparable<? super E>> {

public static final Random RND = new Random();

private void swap(E[] array, int i, int j) {    E tmp = array[i];    array[i] = array[j];    array[j] = tmp;}

private int partition(E[] array, int begin, int end) {    int index = begin + RND.nextInt(end - begin + 1);    E pivot = array[index];    swap(array, index, end);    for (int i = index = begin; i < end; ++i) {        if (array[i].compareTo(pivot) <= 0) {            swap(array, index++, i);        }    }    swap(array, index, end);    return (index);}

private void qsort(E[] array, int begin, int end) {    if (end > begin) {        int index = partition(array, begin, end);        qsort(array, begin, index - 1);        qsort(array, index + 1, end);    }}

public void sort(E[] array) {    qsort(array, 0, array.length - 1);}

}

Kadane //Kadane's algorithm finds the maximum subarray sum in linear time.

Entrada:

Saída:

Código:public class Kadane {

 double maxSubarray(double[] a) {

   double max_so_far = 0;   double max_ending_here = 0;

   for(int i=0; i<a.length; i++) {     max_ending_here = Math.max(0, max_ending_here + a[i]);     max_so_far = Math.max(max_so_far, max_ending_here);   }

   return max_so_far;

 }

}

Bubble Sort//Não alterarhttp://algowiki.net/wiki/index.php/Bubble_sort

Entrada:

Saída:

Código: public static <T extends Comparable<? super T>> T[] bubblesort(T[] input){      boolean swapped;      do{          swapped = false;          for(int i=0; i<input.length-1; i++){              if(input[i].compareTo(input[i+1]) > 0){                  T tmp = input[i];                  input[i] = input[i+1];                  input[i+1] = tmp;                  swapped = true;              }          }      }while(swapped);      return input;  }

Kruskal //Kruskal's algorithm finds a minimum spanning tree for a connected, weighted, undirected graph.http://alogwiki.net

Entrada:

Saída:

Código:   public ArrayList<Edge> getMST(Node[] nodes, ArrayList<Edge> edges){      java.util.Collections.sort(edges);      ArrayList<Edge> MST = new ArrayList<Edge>();      DisjointSet<Node> nodeset = new DisjointSet<Node>();      nodeset.createSubsets(nodes);      for(Edge e : edges){          if(nodeset.find(e.from) != nodeset.find(e.to)){              nodeset.merge(nodeset.find(e.from), nodeset.find(e.to));              MST.add(e);          }      }      return MST;  }

Edmond //Calcula menor ou maior caminho entre dois vértices de um grafo orientadohttp://alogwiki.net

Entrada:

Saída:

Código:public class Edmonds {

  private ArrayList<Node> cycle;

  public AdjacencyList getMinBranching(Node root, AdjacencyList list){      AdjacencyList reverse = list.getReversedList();      // remove all edges entering the root      if(reverse.getAdjacent(root) != null){          reverse.getAdjacent(root).clear();      }      AdjacencyList outEdges = new AdjacencyList();      // for each node, select the edge entering it with smallest weight      for(Node n : reverse.getSourceNodeSet()){          ArrayList<Edge> inEdges = reverse.getAdjacent(n);          if(inEdges.size() == 0) continue;          Edge min = inEdges.get(0);          for(Edge e : inEdges){              if(e.weight < min.weight){                  min = e;              }          }          outEdges.addEdge(min.to, min.from, min.weight);      }

      // detect cycles      ArrayList<ArrayList<Node>> cycles = new ArrayList<ArrayList<Node>>();      cycle = new ArrayList<Node>();      getCycle(root, outEdges);      cycles.add(cycle);      for(Node n : outEdges.getSourceNodeSet()){          if(!n.visited){              cycle = new ArrayList<Node>();              getCycle(n, outEdges);              cycles.add(cycle);          }      }

      // for each cycle formed, modify the path to merge it into another part of the graph      AdjacencyList outEdgesReverse = outEdges.getReversedList();

      for(int i=0; i<cycles.size(); i++){          if(cycles.get(i).contains(root)) continue;          mergeCycles(cycles.get(i), list, reverse, outEdges, outEdgesReverse);      }      return outEdges;  }

  private void mergeCycles(ArrayList<Node> cycle, AdjacencyList list, AdjacencyList reverse, AdjacencyList outEdges, AdjacencyList outEdgesReverse){      ArrayList<Edge> cycleAllInEdges = new ArrayList<Edge>();      Edge minInternalEdge = null;      // find the minimum internal edge weight

      for(Node n : cycle){          for(Edge e : reverse.getAdjacent(n)){              if(cycle.contains(e.to)){                  if(minInternalEdge == null || minInternalEdge.weight > e.weight){                      minInternalEdge = e;                      continue;                  }              }else{                  cycleAllInEdges.add(e);              }          }      }      // find the incoming edge with minimum modified cost      Edge minExternalEdge = null;      int minModifiedWeight = 0;      for(Edge e : cycleAllInEdges){          int w = e.weight - (outEdgesReverse.getAdjacent(e.from).get(0).weight - minInternalEdge.weight);          if(minExternalEdge == null || minModifiedWeight > w){              minExternalEdge = e;              minModifiedWeight = w;          }      }      // add the incoming edge and remove the inner-circuit incoming edge      Edge removing = outEdgesReverse.getAdjacent(minExternalEdge.from).get(0);      outEdgesReverse.getAdjacent(minExternalEdge.from).clear();      outEdgesReverse.addEdge(minExternalEdge.to, minExternalEdge.from, minExternalEdge.weight);      ArrayList<Edge> adj = outEdges.getAdjacent(removing.to);      for(int i=0; i<adj.size(); i++){          if(adj.get(i).to == removing.from){              adj.remove(i);              break;          }      }      outEdges.addEdge(minExternalEdge.to, minExternalEdge.from, minExternalEdge.weight);  }

  private void getCycle(Node n, AdjacencyList outEdges){      n.visited = true;      cycle.add(n);      if(outEdges.getAdjacent(n) == null) return;      for(Edge e : outEdges.getAdjacent(n)){          if(!e.to.visited){              getCycle(e.to, outEdges);          }      }  }}

public class AdjacencyList {

  private Map<Node, ArrayList<Edge>> adjacencies = new HashMap<Node, ArrayList<Edge>>();

  public void addEdge(Node source, Node target, int weight){      ArrayList<Edge> list;      if(!adjacencies.containsKey(source)){          list = new ArrayList<Edge>();          adjacencies.put(source, list);      }else{          list = adjacencies.get(source);      }      list.add(new Edge(source, target, weight));  }

  public ArrayList<Edge> getAdjacent(Node source){      return adjacencies.get(source);  }

  public void reverseEdge(Edge e){      adjacencies.get(e.from).remove(e);      addEdge(e.to, e.from, e.weight);  }

  public void reverseGraph(){      adjacencies = getReversedList().adjacencies;  }

  public AdjacencyList getReversedList(){      AdjacencyList newlist = new AdjacencyList();      for(ArrayList<Edge> edges : adjacencies.values()){          for(Edge e : edges){              newlist.addEdge(e.to, e.from, e.weight);          }      }      return newlist;  }

  public Set<Node> getSourceNodeSet(){      return adjacencies.keySet();  }

  public Collection<Edge> getAllEdges(){      ArrayList<Edge> edges = new ArrayList<Edge>();      for(List<Edge> e : adjacencies.values()){          edges.addAll(e);      }      return edges;  }}

public class Edge implements Comparable<Edge> {

  Node from, to;  int weight;

  Edge(Node f, Node t, int w){      from = f;

      to = t;      weight = w;  }

  public int compareTo(Edge e){      return weight - e.weight;  }}

public class Node implements Comparable<Node> {

  int name;  boolean visited = false;   // used for Kosaraju's algorithm and Edmonds's algorithm  int lowlink = -1;          // used for Tarjan's algorithm  int index = -1;            // used for Tarjan's algorithm  Node(int n){      name = n;  }

  public int compareTo(Node n){      if(n == this)          return 0;      return -1;  }}

Dijkstra //Calcula o menor caminho entre o vértice inicial e os outros nós de um grafo não-orientado

Entrada: graph=matriz com pesos dos vértices, initial=nó inicial, end=nó que se deseja saber o caminho (ou -1 para calcular de todos)

Saída: na posição 0 do array retorna os caminhos mínimos para cada vértice, posição 1 possui o caminho necessário para chegar ao nó (é um vetor, logo v[x], possui o nó anterior à x)

Código:public static Object[] dijkstra(int[][] graph, int initial, int end){

peso[] dists = new peso[graph.length];TreeSet<peso> h = new TreeSet<peso>();int[] paths = new int[graph.length];int z=0;for(int x=0;x<graph.length;x++)

h.add(dists[x] = new peso(initial == x ? 0 : Double.POSITIVE_INFINITY, x));while(!h.isEmpty()){

peso p = h.first();if(p.peso == Double.POSITIVE_INFINITY)

break;h.pollFirst();for(int x=0;x<graph.length;x++)

if(graph[p.vert][x] != 0){

double alt = p.peso + graph[p.vert][x];

if(alt < dists[x].peso){

h.remove(dists[x]);dists[x].peso = alt;paths[x] = p.vert;h.add(dists[x]);

}}

if(p.vert == end)break;

}return new Object[]{ dists, paths };

}

public static class peso implements Comparable<peso>{

double peso;int vert;public peso(double p, int v){ peso = p; vert =v;}public int compareTo(peso o) { return peso < o.peso ? -1 : (peso > o.peso ? 1 : (vert

< o.vert ? -1 : 1)); }}

Crivo de Erastótenes //Descobre todos os números primos menores que um inteiro X

Entrada: x

Saída: array de números primos menores que x

Código:public static Integer[] crivoAristotenes(int limite){

Integer[] i = new Integer[limite+1];int max = (int)Math.floor(Math.sqrt(limite));ArrayList<Integer> primos = new ArrayList<Integer>();for(int x=2;x<=max;x++)

if(i[x] == null){

primos.add(x);for(int y=x+x;y<=limite;y+=x)

i[y] = 0;}for(int x=max+1;x<=limite;x++)

if(i[x]==null)primos.add(x);

return primos.toArray(new Integer[primos.size()]);}

Convex Hull //Em C++; retorna a envoltória convexa de um conjunto de pontos

Entrada:

Saída:

Código:// Implementation of Monotone Chain Convex Hull algorithm.

#include <algorithm>#include <vector>using namespace std;

typedef long long CoordType;

struct Point {CoordType x, y;

bool operator <(const Point &p) const {return x < p.x || (x == p.x && y < p.y);

}};

// 2D cross product.// Return a positive value, if OAB makes a counter-clockwise turn,// negative for clockwise turn, and zero if the points are collinear.CoordType cross(const Point &O, const Point &A, const Point &B){

return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);}

// Returns a list of points on the convex hull in counter-clockwise order.// Note: the last point in the returned list is the same as the first one.vector<Point> convexHull(vector<Point> P){

int n = P.size(), k = 0;vector<Point> H(2*n);

// Sort points lexicographicallysort(P.begin(), P.end());

// Build lower hullfor (int i = 0; i < n; i++) {

while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;H[k++] = P[i];

}

// Build upper hullfor (int i = n-2, t = k+1; i >= 0; i--) {

while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;H[k++] = P[i];

}

H.resize(k);return H;

}

Rotacionando valores de uma matriz

Entrada: matriz que deverá ser rotacionada, angulo (em grau, angulos positivos giram no sentido anti-horário)

Saída: matriz rotacionada pelo angulo

Código:public static int[][] rotate(int[][] m, int a){

int[][] n = new int[m.length][m.length];double radA = Math.toRadians(a);int cosA = (int)Math.cos(radA);int sinA = (int)Math.sin(radA);int x2,y2;int med = (m.length - 1) / 2;for(int x=0;x<m.length;x++)

for(int y=0;y<m.length;y++){

x2 = med + (x - med) * cosA - (y - med) * sinA;y2 = med + (x - med) * sinA + (y - med) * cosA;n[x2][y2] = m[x][y];

}

return n;}

Árvore de Probabilidade //Problema Vampiros

Entrada:

Saída:

Código:

#include <stdio.h>

#define tipo float#define precision 0.0001

tipo probabilidade=0;

iterate(int A, int B, int limit, int val, tipo prob){// printf("A: %d B: %d prob: %f\n", A, B, prob);

if (B<=0){probabilidade += prob;return;

}

if (A<=0)return;

if (prob > precision){iterate(A-val, B+val, limit, val, prob*((tipo)6-limit)/6);iterate(A+val, B-val, limit, val, prob*((tipo)limit)/6);

}}

int main(){int A, B, limit, val;

while(1){scanf("%d", &A);

scanf("%d", &B);scanf("%d", &limit);scanf("%d", &val);

if (A==0 && B==0 && limit==0 && val==0) return;

probabilidade = 0;iterate(A, B, limit, val, 1);//printf("Probabilidade: %f\n", probabilidade*100);printf("%.1f\n", probabilidade*100);

}return;

}

Converte DA Base 10 para K

Entrada: num - inteiro na base 10        baseK - base para a qual o número será convertido

Saída: String que contem o num na base baseK

Código:public static String convertToBase(int num, int baseK){

StringBuilder stb = new StringBuilder();int i;while (num!=0){

i = num % baseK;stb.insert(0, (char)(i+(i>9?87:48)));num /= baseK;

}return stb.toString();

}

Converte PARA a Base 10

Entrada: number    - inteiro que representa o número que será convertido        fromBase  - base na qual number está

Saída: long que representa num na base 10

Observação: Horner's Algorithm -http://www.hitxp.com/math/arth/131202.htmÉ algo que faz diferente do normal. Tenho dúvidas se o overhead ao converter para string compensa a falta dos demais cálculos comuns nesse tipo de conversão, mas acho que sim.

Código:public static long convertToBase10(int number, int fromBase)

   {   String strNum = Integer.toString(number);   long num = (int)strNum.charAt(0) - 48;   for (int x = 1; x < strNum.length(); x++)           num = (num * fromBase) + (int)strNum.charAt(x) - 48;

  return num;

   }

Truncate deixa um número somente com o número de casa especificado

Entrada: f - número        d - número de casas decimais

Saída: número f com precisão de d casa decimais.Todo o resto é removido, NÃO ARREDONDA.

Código:public static float truncate(float f, int d){Double p = Math.pow(10, d);return (float)(Math.floor(f * p) / p);}

Definindo Locale do Scanner e do print //Troca um inteiro de base

Entrada:--

Saída:--

Código:Scanner sc = new Scanner(System.in);sc.useLocale(Locale.ENGLISH);

System.out.format(Locale.ENGLISH, "%d %s %f", inteiro, string, float); //semelhando ao printf

%.3f - ARREDONDA um float para ficar com 3 casas decimais%10.3f - ARREDONDA um float para ficar com 3 casa decimais e utiliza no mínimo 10 caracteres para imprimí-lo (preenche com espaco)Arrendondamento para cima só acontece em caso o número seguinte seja MAIOR que 5.Para nao arredondar utilizar a funcao truncate acima.

float f = 1.1236f;System.out.format(Locale.ENGLISH, "%.3f", f) // "1.124"System.out.format(Locale.ENGLISH, "%10.3f", f) // "     1.124"

Converter Radianos para Graus e vice-versa

Entrada:--

Saída:--

Código:Math.toDegrees(angrad);Math.toRadians(angdeg);

Simplex //Troca um inteiro de base

Entrada:

Saída:

Código:

Primo //Verifica se um número é primo

Entrada: inteiro n

Saída: true ou false

Código:

public static boolean isPrime(long n) {boolean prime = true;int limit = Math.sqrt(n);for (long i = 3; i <= limit; i += 2)

if (n % i == 0) {prime = false;break;

}if (( n%2 !=0 && prime && n > 2) || n == 2) {

return true;} else {

return false;}

}

Sub Set Sum //Mochila

Entrada:

Saída:

Código:

package javaapplication1;

import java.util.Arrays;

public class Main {    //retorna true se existe uma combinacao de elementos de    //vetor de valor val    //Entradas:    //vetor: um vetor de inteiros ordenado    //n: número de elementos no vetor    //val: valor do peso total    static boolean mochila(int vetor[], int soma[], int n, int val){        System.out.println("n: " + n + " val: " + val);        if (n<=0) return false;

        if (val > soma[n-1]) return false;

        int i=n-1;        while(i>-1 && vetor[i]>val) i--;        if (i == -1)            return false;

        if (vetor[i] == val)            return true;

        boolean ret = mochila(vetor, soma, i, val-vetor[i]);        if (ret) return true;        else return mochila(vetor, soma, i, val);    }

    public static void main(String[] args) {        int n = 1000;        int vetor[]= new int[n];        for (int i=0; i<n ; i++){            vetor[i] = (int) (Math.random() * n);        }        Arrays.sort(vetor);

        int vetorSoma[]= new int[n];        vetorSoma[0]=vetor[0];        for (int i=1; i<n ; i++){            vetorSoma[i] = vetorSoma[i-1]+vetor[i];        }

        for (int i=0; i<n ; i++)            System.out.print(vetor[i] + "  ");        System.out.println();        for (int i=0; i<n ; i++)            System.out.print(vetorSoma[i] + "  ");        System.out.println();

        System.out.println("Resultado: " + mochila(vetor, vetorSoma, n, vetorSoma[n-1]/2));    }}

Resolvedor de Sistemas Lineares //Resolve um sistema linear de equações

Entrada:

Saída:

Código:

Gerador de entradas //Algoritmo gerador de grandes entradas

Entrada:

Saída:

Código:

Dijkstra //Algoritmo para o caminho mais curto

Entrada:

Saída:

Código:

Tempo //Métodos para manipulação de tempo

Entrada:

Saída:

Código:

MDC //Métodos para encontrar o Máximo Divisor Comum (algoritmo de euclides)

Entrada: Integers x, y such that x >= y and y > 0

Saída: inteiro

int gcd(int x, int y){if (y == 0)

return x;else

return gcd(y, x % y);}

MMC //Métodos para encontrar o Mínimo Divisor Comum

Entrada:

Saída:

Código:

public int lcm(int a, int b){        if (a == 0 ||  b == 0)            return 0;

        int index = 1;        int test = a*index;

        while (test <= a*b)        {            if (test % b == 0)                return test;

            index++;            test = a * index;        }       return a*b;}

GEOMETRIA

Operações com retas e pontos

colineares // verifica se os pontos A, B e P são colineares

Entrada: 3 pontos

Saída: booleano indicando se os pontos são colineares

public static boolean colineares(Ponto2D A, Ponto2D B, Ponto2D P){        double dx = B.x - A.x, dy = B.y - A.y,        eps = 0.001 * (dx * dx + dy * dy);        return (A.x != B.x && (A.x <= P.x && P.x <= B.x || B.x <= P.x && P.x <= A.x)        || A.x == B.x && (A.y <= P.y && P.y <= B.y || B.y <= P.y && P.y <= A.y))        && Math.abs(area2(A, B, P)) < eps;}

projecao // verifica se a projeção de P no segmento AB coincide com A ou B

Entrada: 3 pontos

Saída: booleano ...

public static boolean projecao(Ponto2D A, Ponto2D B, Ponto2D P){        double dx = B.x - A.x, dy = B.y - A.y;        double eps = 0.001 * (dx * dx + dy * dy);        double len2 = dx * dx + dy * dy;        double inprod = dx * (P.x - A.x) + dy * (P.y - A.y);        return inprod > -eps && inprod < len2 + eps;}

projPAB // retorna a projeção do ponto P no segmento AB

Entrada: 3 pontos

Saída: o ponto de projeção de P no segmento AB

public static Ponto2D projPAB(Ponto2D A, Ponto2D B, Ponto2D P){        double vx = B.x - A.x, vy = B.y - A.y, len2 = vx * vx + vy * vy;        double inprod = vx * (P.x - A.x) + vy * (P.y - A.y);        return new Ponto2D(A.x + inprod * vx/len2, A.y + inprod * vy/len2);}

projPAB // retorna a projeção do ponto P no segmento AB; usa a equação da reta : ax + by + c = 0

Entrada: os coeficientes da reta e o ponto P

Saída: o ponto de projeção de P na reta de coeficientes a, b, c

public static Ponto2D projPAB(double a, double b, double c, Ponto2D P){        double d = P.x * a + P.y * b + c;        return new Ponto2D(P.x - d * a, P.y - d * b);}

distance2 // retorna o quadrado da distância entre P e Q

Entrada: dois pontos

Saída: o quadrado da distância entre eles

public static double distance2(Ponto2D P, Ponto2D Q){        double dx = P.x - Q.x;        double dy = P.y - Q.y;        return dx * dx + dy * dy;}

getM // calcula o coeficiente angular da reta

Entrada: dois pontos de uma reta

Saída: o coeficiente angular da reta

public static double getM(Ponto2D A, Ponto2D B){        return (A.y - B.y)/(A.x - B.x);}

getAlpha // calcula o ângulo da reta (associado ao coeficiente angular)

Entrada: dois pontos

Saída: o ângulo da reta

public static double getAlpha(Ponto2D A, Ponto2D B){        return Math.atan(getM(A, B));}

lado // verifica em que lado da reta AB o ponto P está; -1 : esquerda de AB; 1 : direita de AB; 0 : pertence à AB

Entrada: 3 pontos

Saída: inteiro indicando o lado em que o ponto se encontra

public static int lado(Ponto2D A, Ponto2D B, Ponto2D P){        double s = A.x*P.y - A.y*P.x + A.y*B.x - A.x*B.y + P.x*B.y - P.y*B.x;        return s<0 ? -1 : (s>0 ? 1 : 0);}

Operações com triângulos

area2 // calcula o dobro da área orientada de um triângulo

Entrada: os 3 vértices de um triângulo

Saída: o dobro da área orientada do triângulo - double

public static double area2(Ponto2D A, Ponto2D B, Ponto2D C){        return (A.x - C.x) * (B.y - C.y) - (A.y - C.y) * (B.x - C.x);}

areaTriangulo // calcula a área de um triângulo

Entrada: os 3 vértices de um triângulo

Saída: a área do triângulo - double

public static double areaTriangulo(Ponto2D A, Ponto2D B, Ponto2D C){        return Math.abs(area2(A, B, C))*0.5;}

triangulate // faz a triangulação num dado polígono; retorna a lista de triangulos encontrados

Entrada: um vetor de pontos representando o polígono

Saída: uma lista de triângulos encontrados

public static List<Triangulo> triangulate(Ponto2D[] pol){        int n = pol.length, j = n - 1, iA = 0, iB, iC;        int[] next = new int[n];        List<Triangulo> lista = new ArrayList<Triangulo>();        for (int i=0; i<n; i++){            next[j] = i;            j = i;        }        for (int k=0; k<n-2; k++){            Ponto2D a, b, c;            boolean triaFound = false;            int count = 0;            while (!triaFound && ++count < n){                iB = next[iA]; iC = next[iB];                a = pol[iA]; b = pol[iB]; c = pol[iC];                if (area2(a, b, c) >= 0){                    j = next[iC];                    while (j != iA && !pertenceTriangulo(a, b, c, pol[j])){                        j = next[j];                    }                    if (j == iA){                        lista.add(new Triangulo(a, b, c));                        next[iA] = iC;                        triaFound = true;                    }                }                iA = next[iA];            }        }        return lista;}

baricentro // encontra o baricentro do triângulo

Entrada: 3 pontos

Saída: o baricentro do triângulo

public static Ponto2D baricentro(Ponto2D A, Ponto2D B, Ponto2D C){        double x = (A.x + B.x + C.x)/3;        double y = (A.y + B.y + C.y)/3;        return new Ponto2D(x, y);}

Operações com polígonos

PoligonoConvexo // verifica se um dado polígono é convexo

Entrada: um vetor de pontos de duas dimensões

Saída: booleano indicando se o polígono é convexo

public static boolean PoligonoConvexo(Ponto2D[] p){        int n = p.length,k=0;        for (int i=1; i<n; i++)          if (p[i].x <= p[k].x && (p[i].x < p[k].x || p[i].y < p[k].y))             k=i;        int prev = k - 1, next = k + 1;        if (prev == -1) prev = n - 1;        if (next == n) next = 0;        return area2(p[prev], p[k], p[next]) > 0;}

pertencePoligono // verifica se o ponto P pertence ao polígono

Entrada: ponto P e um vetor de pontos indicando o polígono

Saída: booleano indicando se o ponto pertence ao polígono

public static boolean pertencePoligono(Ponto2D P, Ponto2D[] pol){        int n = pol.length, j = n - 1;        boolean b = false;        double x = P.x, y = P.y;        for (int i=0; i<n; i++){            if (pol[j].y <= y && y < pol[i].y && areaTriangulo(pol[j], pol[i], P) > 0 ||            pol[i].y <= y && y < pol[j].y && areaTriangulo(pol[i], pol[j], P) > 0){                b = !b;            }            j = i;        }        return b;    }

areaPoligono // calcula a area de um poligono convexo qualquer

Entrada: vetor de pontos de duas dimensões

Saída: a área do poligono P - double

public static double areaPoligono(Ponto2D[] pol){

        int n = pol.length,        j = n - 1;        float a = 0;        for(int i=0; i<n; i++){            a += pol[j].x * pol[i].y - pol[j].y * pol[i].x;            j = i;        }        return a;}

Operações com círculos e circunferências

areaCirculo // calcula a área de um círculo

Entrada: o raio do círculo

Saída: a área do círculo

public static double areaCirculo(double r){        return Math.PI*r*r;}

setorCircular // calcula a área de um setor circular

Entrada: o raio do círculo e o ângulo do setor circular

Saída: a área do setor circular

public static double setorCircular(double r, double alfa){        return alfa*areaCirculo(r)/360;}

pertence // verifica se o ponto P pertence ao círculo

Entrada: o centro do círculo, o raio e o ponto P

Saída: booleano indicando se P pertence ao círculo

public static boolean pertence(Ponto2D C, double r, Ponto2D P){        return Math.pow(P.x - C.x, 2) + Math.pow(P.y - C.y, 2) - Math.pow(r, 2) <= 0;}

interceptaCirculo // verifica se a reta que contém P e de angulo alfa intercepta o círculo de centro C e raio r

Entrada: ponto P e ângulo alfa representando uma reta; ponto C e raio r representando um círculo

Saída: booleano indicando se a reta intercepta o círculo

public static boolean interceptaCirculo(Ponto2D P, double alfa, Ponto2D C, double r){        double tan = Math.tan(alfa);        double tan2 = tan*tan;        double a = 1 + tan2;

        double b = -2*C.x - 2*P.x*tan2 + 2*P.y*tan - 2*C.y*tan;        double c = C.x*C.x + P.y*P.y + tan2*P.x*P.x + C.y*C.y - 2*P.x*P.y*tan - 2*C.y*P.y + 2*C.y*P.x*tan - r*r;        return b*b - 4*a*c >= 0;}

intersecaoCirculo // retorna os pontos de interseção de uma circunferência com uma reta

Entrada: ponto P e ângulo alfa representando uma reta; ponto C e raio r representando um círculo

Saída: os pontos de interseção entre a reta e o círculo, se existirem

public static Ponto2D[] intersecaoCirculo(Ponto2D P, double alfa, Ponto2D C, double r){        double tan = Math.tan(alfa);        double tan2 = tan*tan;        double a = 1 + tan2;        double b = -2*C.x - 2*P.x*tan2 + 2*P.y*tan - 2*C.y*tan;        double c = C.x*C.x + P.y*P.y + tan2*P.x*P.x + C.y*C.y - 2*P.x*P.y*tan - 2*C.y*P.y + 2*C.y*P.x*tan - r*r;        double delta = b*b - 4*a*c;        if(delta < 0){            return null;        }        else if(delta == 0){            double xt = -b/(2*a);            return new Ponto2D[]{new Ponto2D(xt, P.y - tan*(P.x - xt))};        }        else{            double xt1 = (-b + Math.sqrt(delta))/(2*a);            double xt2 = (-b - Math.sqrt(delta))/(2*a);            Ponto2D t1 = new Ponto2D(xt1, P.y - tan*(P.x - xt1));            Ponto2D t2 = new Ponto2D(xt1, P.y - tan*(P.x - xt2));            return new Ponto2D[]{t1, t2};        }}

pontosTangencia // retorna os pontos de tangência de uma circunferência em relação a um ponto P externo****** não está totalmente correto **********

Entrada: ponto C e raio r representando um círculo; ponto externo P

Saída: os pontos de tangência

public static Ponto2D[] pontosTangencia(Ponto2D C, double r, Ponto2D P){        double difX = (P.x - C.x)*(P.x - C.x);        double difY = (P.y - C.y)*(P.y - C.y);        double a = difX + difY;        double b = 2*(P.x - C.x)*(C.x*C.x - C.x*P.x - r*r) - 2*C.x*difY;        double c = difY*C.x*C.x + Math.pow(C.x*C.x - C.x*P.x - r*r, 2) - difY*r*r;

        double delta = b*b - 4*a*c;        double x1 = (-b + Math.sqrt(delta))/(2*a);        double x2 = (-b - Math.sqrt(delta))/(2*a);

        double y1 = C.y + Math.sqrt(r*r - (x1 - C.x)*(x1 - C.x));        double y2 = C.y - Math.sqrt(r*r - (x1 - C.x)*(x1 - C.x));        double y3 = C.y + Math.sqrt(r*r - (x2 - C.x)*(x2 - C.x));        double y4 = C.y - Math.sqrt(r*r - (x2 - C.x)*(x2 - C.x));

        return new Ponto2D[]{new Ponto2D(x1, y1), new Ponto2D(x1, y2), new Ponto2D(x2, y3), new Ponto2D(x2,y4)};}

Fim dos métodos de geometria

baskara // retorna as raízes de uma equação do segundo grau - não considera o caso em que delta =0

Entrada: coeficientes a, b ec

Saída: um vetor contendo as raízes

public static double[] baskara(double a, double b, double c){        double delta = b*b - 4*a*c;        if(delta >= -0.00001 || delta <= 0.00001){            return new double[]{-b/(2*a)};        }        else{            return new double[]{(-b + Math.sqrt(delta))/(2*a), (-b - Math.sqrt(delta))/(2*a) };        }    }

Fatorial //super otimizado

Entrada: n

Saída: n!

static long currentN;//http://www.luschny.de/math/factorial/FastFactorialFunctions.htmpublic static BigInteger Factorial(int n)

{     if (n < 2) return BigInteger.ONE;

    BigInteger p = BigInteger.ONE,r = BigInteger.ONE;     currentN = 1;     int h = 0, shift = 0, high = 1;     int log2n = (int)Math.floor(Math.log10(n) / Math.log10(2));

    while (h != n)     {         shift += h;         h = n >> log2n--;         int len = high;         high = (h - 1) | 1;         len = (high - len) / 2;

        if (len > 0)         {             p = p.multiply(Product(len));             r = r.multiply(p);         }     }

    return r.shiftLeft(shift); }

private static BigInteger Product(int n) {     int m = n / 2;     if (m == 0) return BigInteger.valueOf(currentN +=2);     if (n == 2) return BigInteger.valueOf((currentN += 2) * (currentN += 2));     return Product(n - m).multiply(Product(m)); }

Permutação //quantos conjuntos de R elemento é possível fazer com N objetos (sem repetir objeto dentro do conjunto)

Entrada: n = número de elementos / r = tamanho dos conjuntos

Saída: número de conjuntos possíveis

public static long permutacao(int n, int r){return Factorial(n).divide(Factorial(n -r)).longValue();}

Graham //define o envoltório convexo em um plano 2D PASSAR PARA JAVA AINDA

Entrada: n = número de elementos / r = tamanho dos conjuntos

Saída: número de conjuntos possíveis

 class Point{ public:   double x,y;   Point(double _x,double _y){x=_x;y=_y;};   Point(){x=0.0;y=0.0;}; };

 //------------------------------------------

 //indice do ponto mais baixo int get_lower_point_id(vector<Point> &in_point) {   double min_y = in_point[0].y;   int id_min;   for(int i=0; i < in_point.size(); ++i)

if(in_point[i].y < min_y ) {   min_y = in_point[i].y ;   id_min = i;

} //cout << "id_min= " << id_min << "\n"; return id_min;

 }

 //-------------------------------------------------------------

 double compute_angle(double ox, double oy, double x1, double y1) {   //                         + (x1,y1)   //                        /   //                       /   //                      /   //                     /   //                    /   angle   //       ------------+-----------------   //                   (ox,oy)   //                    .   //         angle   .    .   //       ------------+-----------------   //                 .. \   //                     \   //                      \   //                       \   //                        \   //                         \   //                         (x1,y1)   //   //   //

   double angle;

   x1=x1-ox;   y1=y1-oy;   if (y1 >=0)

angle = acos(x1/(sqrt(x1*x1+y1*y1)));   else

angle = 2.0*PI - acos(x1/(sqrt(x1*x1+y1*y1)));

   //cout << angle << "x1= " << x1 << "y1= " << y1 << "x2= " << x2 << "y2= " << y2 << "\n";   return angle; } //------------------------------------------- bool compute_is_left_curve(double v1x,double v1y,double v2x, double v2y, double v3x, double v3y) {   //produto vetorial (v1-v2)x(v3-v2)   double prod_vetorial =(v1x-v2x)*(v3y-v2y)-(v3x-v2x)*(v1y-v2y);

   if (prod_vetorial==0) cout<<"zero \n";

   if( prod_vetorial > 0)

return true;   else

return false; };

 //-------------------------------------------

 typedef pair<double,int> anglepoint; void Graham(vector<Point> &in_points,vector<Point> &fecho_points) {   fecho_points.clear();   int min_y_point_id = get_lower_point_id(in_points);

   //temos que colocar o ponto min_y_point_id na posicao zero   Point temp_front_point = in_points[0];   in_points[0] = in_points[min_y_point_id];   in_points[min_y_point_id] = temp_front_point ;

   vector<anglepoint> list_ord;

   for (int i=1;i<in_points.size();++i)   {

//computar o ângulo entre o elemento 0 e o i-esimo elemento double angle  = compute_angle(in_points[0].x, in_points[0].y,

in_points[i].x,in_points[i].y); list_ord.push_back(anglepoint( angle , i ) );

   }   //ordenado pelo ângulo   sort(list_ord.begin(), list_ord.end());

   //for (int i=0; i<list_ord.size(); ++i)   //cout<<"an - "<<list_ord[i].first<<"id- "<<list_ord[i].second<<"\n";

   fecho_points.push_back(in_points[0]);   fecho_points.push_back(in_points[list_ord[0].second]);   fecho_points.push_back(in_points[list_ord[1].second]);

   for (int i=2;i<list_ord.size();++i)   {

int id = list_ord[i].second; fecho_points.push_back(in_points[id]);

//testar últimos 3 elementos da lista

//else kill ate ser positivo while (!compute_is_left_curve(fecho_points[fecho_points.size()-1].x,   fecho_points[fecho_points.size()-1].y,   fecho_points[fecho_points.size()-2].x,   fecho_points[fecho_points.size()-2].y,   fecho_points[fecho_points.size()-3].x,   fecho_points[fecho_points.size()-3].y) && fecho_points.size()>3 ) {   Point temp1 = fecho_points[fecho_points.size()-1];

  fecho_points.pop_back();   fecho_points.pop_back();   fecho_points.push_back( temp1 ); }

   }

 }

Para o dia da prova

-> levar um dicionário