Cod sursa(job #1980032)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 11 mai 2017 23:14:45
Problema Rays Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX_N = 2.e5;

struct Punct {
  int x;
  int y;
};

struct Baleiere {
  Punct P;
  int index;
  bool tip;

  bool operator < (const Baleiere& other) const {
    if (P.y * other.P.x == other.P.y * P.x)
      return tip > other.tip;
    return P.y * other.P.x > other.P.y * P.x;
  }
};

int N;
int kPozitiv, kNegativ;
int raze;

int viz[MAX_N + 5];

Baleiere rezolvaPozitiv[2 * MAX_N + 5];
Baleiere rezolvaNegativ[2 * MAX_N + 5];

int rezolva(Baleiere rez[], int K) {
  sort(rez + 1, rez + K + 1);

  int ans = 0;

  for (int i = 1; i <= K; ++i) {
    if (rez[i].tip == 1)
      viz[rez[i].index] = ans + 1;
    else if (viz[rez[i].index] == ans + 1)
      ans++;
  }

  return ans;
}

int main() {
  freopen("rays.in", "r", stdin);
  freopen("rays.out", "w", stdout);

  scanf("%d", &N);

  for (int i = 1; i <= N; ++i) {
    int x, y1, y2;
    scanf("%d%d%d", &x, &y1, &y2);

    if (y1 < y2)
      swap(y1, y2);

    if (x > 0) {
      rezolvaPozitiv[++kPozitiv] = {{x, y1}, i, 1};
      rezolvaPozitiv[++kPozitiv] = {{x, y2}, i, 0};
    } else { /// x < 0
      rezolvaNegativ[++kNegativ] = {{x, y1}, i, 0};
      rezolvaNegativ[++kNegativ] = {{x, y2}, i, 1};
    }
  }

  raze += rezolva(rezolvaPozitiv, kPozitiv);
  raze += rezolva(rezolvaNegativ, kNegativ);

  printf("%d\n", raze);

  return 0;
}