Submission #260159

#	Time	Username	Problem	Language	Result	Execution time	Memory
260159		tincamatei	Printed Circuit Board (CEOI12_circuit)	C++14	35 / 100	126 ms	11108 KiB

circuit

#include <bits/stdc++.h>

const int MAX_N = 100000;

struct Fraction {
  int a, b;

  Fraction() {
    a = 0;
    b = 1;
  }

  Fraction(int _a, int _b) {
    a = _a;
    b = _b;
    if(b < 0) {
      a = -a;
      b = -b;
    }
  }

  bool operator== (const Fraction x) const {
    return (long long)a * x.b == (long long)b * x.a;
  }

  bool operator< (const Fraction x) const {
    return (long long)a * x.b < b * x.a;
  }

  bool operator!= (const Fraction x) const {
    return !(*this == x);
  }
};

struct Point {
  int x, y;
  Fraction slope;
} points[MAX_N];
bool marked[MAX_N];

static inline long long detarea(int a, int b) {
  return (long long)points[a].x * points[b].y - (long long)points[a].y * points[b].x;
}

static inline long long quadarea(int a, int b, int c, int d) {
  return detarea(a, b) + detarea(b, c) + detarea(c, d) + detarea(d, a);
}

static inline long long triarea(int a, int b, int c) {
  return detarea(a, b) + detarea(b, c) + detarea(c, a);
}

struct Segment {
  int a, b;

  bool operator< (const Segment x) const {
    if(b == x.a)
      return true;
    if(a == x.b)
      return false;
    long long area = quadarea(a, b, x.b, x.a);
    if(area == 0)
      return points[a].x < points[x.a].x;
    return area < 0; 
  }
} segments[MAX_N];

struct Event {
  Fraction t;
  int type, segmentId;
};

bool cmp(Event a, Event b) {
  return a.t < b.t || (a.t == b.t && a.type < b.type);
}

int main() {
  int N;
  scanf("%d", &N);
  for(int i = 0; i < N; ++i) {
    scanf("%d%d", &points[i].x, &points[i].y);
    points[i].slope = Fraction(points[i].y, points[i].x);
    segments[i] = {i, (i + 1) % N};
  }

  std::vector<Event> ev;

  for(int i = 0; i < N; ++i) {
    if(points[segments[i].b].slope < points[segments[i].a].slope)
      std::swap(segments[i].a, segments[i].b);
    else if(points[segments[i].b].slope == points[segments[i].a].slope &&
            points[segments[i].b].x > points[segments[i].a].x)
      std::swap(segments[i].a, segments[i].b);
      
    ev.push_back({points[segments[i].a].slope, 0, i});
    ev.push_back({points[segments[i].b].slope, 2, i});
    ev.push_back({points[i].slope, 1, i});
  }

  std::sort(ev.begin(), ev.end(), cmp);
  std::set<Segment> segs;

  Fraction last_slope;
  int best_point = -1;

  // I feel like Yandere-dev
  for(int i = 0; i < 3 * N; ++i) {
    //printf("Event: %d %d-%d\n", ev[i].type,
    //                            segments[ev[i].segmentId].a + 1,
    //                            segments[ev[i].segmentId].b + 1);
    if(ev[i].type == 0) {
      if(points[segments[ev[i].segmentId].a].slope == // Am un segment cu aceleasi pante la origine
         points[segments[ev[i].segmentId].b].slope) {
        if(points[segments[ev[i].segmentId].a].slope == last_slope) { // last_slope e updatat
          if(points[segments[ev[i].segmentId].a].x < points[best_point].x) { // vad punctul cel mai
          // aproape de origine
            best_point = segments[ev[i].segmentId].a;
          }
        } else {
          last_slope = points[segments[ev[i].segmentId].a].slope;
          best_point = segments[ev[i].segmentId].a;
        }
      } else {
        segs.insert(segments[ev[i].segmentId]);
      }
    } else if(ev[i].type == 2) {
      if(points[segments[ev[i].segmentId].a].slope != 
         points[segments[ev[i].segmentId].b].slope)
        segs.erase(segments[ev[i].segmentId]);
    } else {
      if(segs.empty()) {
        marked[best_point] = true;
      } else {
        Segment firstseg = *segs.begin();
        if(last_slope != ev[i].t) {
          last_slope = ev[i].t;
          best_point = -1;
        }

        if(points[firstseg.a].slope == last_slope &&
          (best_point == -1 || (best_point != -1 && points[firstseg.a].x < points[best_point].x)))
          best_point = firstseg.a;
        if(points[firstseg.b].slope == last_slope &&
          (best_point == -1 || (best_point != -1 && points[firstseg.b].x < points[best_point].x)))
          best_point = firstseg.b;
      
        if(best_point != -1)
          marked[best_point] = true;
      }
    }

    //printf("Debug segments:\n");
    //for(auto it: segs) {
    //  printf("[%d %d]\n", it.a + 1, it.b + 1);
    //}
  }

  //printf("??%d %d\n", segments[2] < segments[3], segments[3] < segments[2]);
  //printf("%lld\n", quadarea(segments[2].a, segments[2].b, segments[3].b, segments[3].a));
  //printf("%lld\n", quadarea(segments[2].a, segments[2].b, segments[3].a, segments[3].b));

  int res = 0;
  for(int i = 0; i < N; ++i)
    if(marked[i])
      ++res;

  printf("%d\n", res);
  for(int i = 0; i < N; ++i)
    if(marked[i])
      printf("%d ", i + 1);
	return 0;
}

Compilation message (stderr)

circuit.cpp: In function 'int main()':
circuit.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
circuit.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &points[i].x, &points[i].y);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 35 / 100