Cod sursa(job #2681102)

Utilizator teochess2017Togan Teodor-Bogdan teochess2017 Data 4 decembrie 2020 22:54:58
Problema Patrate 3 Scor 100
Compilator c-64 Status done
Runda Arhiva de probleme Marime 3.73 kb
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

int v[2][1000];
int pct1[2], pct2[2], pctcautat[2];

FILE *fin, *fout;

int readInt(){
  int n;
  char ch, tch = 0;
  while(!isdigit(ch = fgetc(fin))){
    tch = ch;
  }
  if(tch == '-'){
    tch = -1;
  }else{
    tch = 1;
  }
  n = ch - '0';
  while(isdigit(ch = fgetc(fin))){
    n = n * 10 + ch - '0';
  }
  while(isdigit(ch = fgetc(fin))){
    n = n * 10 + ch - '0';
  }
  return n * tch;
}
void quicksort(int min, int max, int tip){
  int b, e, piv, aux;
  b = min;
  e = max;
  piv = v[tip][(min + max) / 2];
  while(piv > v[tip][b]){
    b++;
  }
  while(piv < v[tip][e]){
    e--;
  }
  while(b < e){
    aux = v[tip][b];
    v[tip][b] = v[tip][e];
    v[tip][e] = aux;
    aux = v[(tip + 1) % 2][b];
    v[(tip + 1) % 2][b] = v[(tip + 1) % 2][e];
    v[(tip + 1) % 2][e] = aux;
    do{
      b++;
    }while(piv > v[tip][b]);
    do{
      e--;
    }while(piv < v[tip][e]);
  }
  if(min < e){
    quicksort(min, e, tip);
  }
  if((e + 1) < max){
    quicksort(e + 1, max, tip);
  }
}
int cautare(int n, int coordl, int coordc){
  int min, max, mij;
  min = 0;
  max = n;
  while((max - min) > 1){
    mij = (max + min) / 2;
    if((coordl < v[0][mij]) || ((coordl == v[0][mij]) && (coordc < v[1][mij]))){
      max = mij;
    }else{
      min = mij;
    }
  }
  return min;
}
int verificare(int n){
  int pozret;
  pozret = cautare(n, pctcautat[0], pctcautat[1]);
  if((pctcautat[0] != v[0][pozret]) || (pctcautat[1] != v[1][pozret])){
    return 1;
  }else{
    return 0;
  }
}

int main()
{
    int n, i, j, caz, st, difl, difc, nrp;
    fin = fopen("patrate3.in", "r");
    fscanf(fin, "%d", &n);
    for(i = 0; i < n; i++){
      v[0][i] = readInt();
      v[1][i] = readInt();
    }
    fclose(fin);
    quicksort(0, n - 1, 0);
    j = 0;
    for(i = 1; i < n; i++){
      if(v[0][i] != v[0][i - 1]){
        quicksort(j, i - 1, 1);
        j = i;
      }
    }
    quicksort(j, i - 1, 1);
    nrp = 0;
    for(i = 0; i < n; i++){
      for(j = i + 1; j < n; j++){
        if(v[0][i] <= v[0][j]){
          if(v[1][i] <= v[1][j]){
            caz = 1;
            pct1[0] = v[0][i];
            pct1[1] = v[1][i];
            pct2[0] = v[0][j];
            pct2[1] = v[1][j];
          }else{
            caz = 2;
            pct1[0] = v[0][j];
            pct1[1] = v[1][j];
            pct2[0] = v[0][i];
            pct2[1] = v[1][i];
          }
        }else{
          if(v[1][j] <= v[1][i]){
            caz = 1;
            pct1[0] = v[0][j];
            pct1[1] = v[1][j];
            pct2[0] = v[0][i];
            pct2[1] = v[1][i];
          }else{
            caz = 2;
            pct1[0] = v[0][i];
            pct1[1] = v[1][i];
            pct2[0] = v[0][j];
            pct2[1] = v[1][j];
          }
        }
        st = 0;
        if(caz == 1){
          difl = pct2[0] - pct1[0];
          difc = pct2[1] - pct1[1];
          pctcautat[0] = pct1[0] - difc;
          pctcautat[1] = pct1[1] + difl;
          st += verificare(n);
          pctcautat[0] = pctcautat[0] + difl;
          pctcautat[1] = pctcautat[1] + difc;
          st += verificare(n);
        }else{
          difl = pct1[0] - pct2[0];
          difc = pct2[1] - pct1[1];
          pctcautat[0] = pct1[0] - difc;
          pctcautat[1] = pct1[1] - difl;
          st += verificare(n);
          pctcautat[0] = pctcautat[0] - difl;
          pctcautat[1] = pctcautat[1] + difc;
          st += verificare(n);
        }
        if(st == 0){
          nrp++;
        }
      }
    }
    fout = fopen("patrate3.out", "w");
    fprintf(fout, "%d", nrp / 2);
    fclose(fout);
    return 0;
}