oj.uz

Submission #260120

# Submission time Handle Problem Language Result Execution time Memory
260120 2020-08-09T10:47:33 Z tincamatei Printed Circuit Board (CEOI12_circuit) C++14
40 / 100
 100 ms 11108 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 {
    long long area = quadarea(a, b, x.b, x.a);

    if(area < 0)
      return true;
    if(area == 0)
      return points[a].x < points[x.a].x;
    return false;
  }
} 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.begin();
      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:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
circuit.cpp:72: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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 3 ms 2048 KB Output is correct
3 Correct 3 ms 2304 KB Output is correct
4 Correct 7 ms 2340 KB Output is correct
5 Incorrect 11 ms 2972 KB Output isn't correct
6 Incorrect 12 ms 2936 KB Output isn't correct
7 Incorrect 20 ms 3448 KB Output isn't correct
8 Incorrect 9 ms 2808 KB Output isn't correct
9 Correct 11 ms 2684 KB Output is correct
10 Incorrect 12 ms 2980 KB Output isn't correct
11 Incorrect 12 ms 3320 KB Output isn't correct
12 Correct 21 ms 3324 KB Output is correct
13 Incorrect 35 ms 4468 KB Output isn't correct
14 Correct 39 ms 4468 KB Output is correct
15 Correct 59 ms 6640 KB Output is correct
16 Execution timed out 110 ms 11108 KB Time limit exceeded
17 Execution timed out 131 ms 11108 KB Time limit exceeded
18 Execution timed out 32 ms 2808 KB Time limit exceeded (wall clock)
19 Execution timed out 32 ms 2808 KB Time limit exceeded (wall clock)
20 Execution timed out 29 ms 2808 KB Time limit exceeded (wall clock)