oj.uz

Submission #260114

# Submission time Handle Problem Language Result Execution time Memory
260114 2020-08-09T10:42:40 Z tincamatei Printed Circuit Board (CEOI12_circuit) C++14
15 / 100
 100 ms 12516 KB 
#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;
  }
};

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);
}

struct Segment {
  int a, b;

  bool operator< (const Segment x) const {
    return quadarea(a, b, x.b, x.a) > 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;

  for(int i = 0; i < 3 * N; ++i) {
    if(ev[i].type == 0)
      segs.insert(segments[ev[i].segmentId]);
    else if(ev[i].type == 2)
      segs.erase(segments[ev[i].segmentId]);
    else {
      Segment firstseg = *segs.rbegin();
      if(points[firstseg.a].slope == points[firstseg.b].slope)
        marked[ev[i].segmentId] = (ev[i].segmentId == firstseg.a);
      else
        marked[ev[i].segmentId] = (ev[i].segmentId == firstseg.a ||
                                   ev[i].segmentId == firstseg.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

circuit.cpp: In function 'int main()':
circuit.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
circuit.cpp:66: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
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1920 KB Output isn't correct
2 Runtime error 4 ms 3840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 6 ms 4220 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 6 ms 2304 KB Output is correct
5 Incorrect 10 ms 2936 KB Output isn't correct
6 Incorrect 10 ms 2936 KB Output isn't correct
7 Incorrect 19 ms 3576 KB Output isn't correct
8 Runtime error 9 ms 4856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 15 ms 2684 KB Output is correct
10 Incorrect 11 ms 2936 KB Output isn't correct
11 Incorrect 11 ms 3320 KB Output isn't correct
12 Correct 18 ms 3448 KB Output is correct
13 Incorrect 33 ms 4724 KB Output isn't correct
14 Runtime error 43 ms 8804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 54 ms 10204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Incorrect 84 ms 12260 KB Output isn't correct
17 Execution timed out 113 ms 12516 KB Time limit exceeded
18 Execution timed out 33 ms 4088 KB Time limit exceeded (wall clock)
19 Execution timed out 30 ms 4096 KB Time limit exceeded (wall clock)
20 Execution timed out 33 ms 4224 KB Time limit exceeded (wall clock)