QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#935105#2297. Flatland OlympicsAngelOlanWA 2ms3968kbC++232.2kb2025-03-15 12:46:342025-03-15 12:46:43

Judging History

This is the latest submission verdict.

  • [2025-03-15 12:46:43]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 3968kb
  • [2025-03-15 12:46:34]
  • Submitted

answer

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
// Pura Gente del Coach Moy y de la Alexbriza

using ll = long long;
using T = ll;

struct Point {
  int x, y;

  Point() {}
  Point(int x, int y) : x(x), y(y) {}

  void read() {
    cin >> x >> y;
  }

  void print() {
    cout << x << ' ' << y << '\n';
  }

  T sq() { return (T)x * x + (T)y * y; }

  T dot(Point p) { return (T)x * p.x + (T)y * p.y; }
  T cross(Point p) const { return (T)x * p.y - (T)y * p.x; }

  Point operator-(Point p) const { return Point(x - p.x, y - p.y); }
};

T orient(Point a, Point b) { return a.cross(b); }

int half(Point p, Point v) { return v.cross(p) < 0 || (v.cross(p) == 0 && v.dot(p) < 0); }

inline void polarSortAround(Point o, Point dir, vector<Point>& P, bool inv = false) {
  sort(P.begin(), P.end(), [&](Point p, Point q) -> bool {
    auto ta = make_tuple(half(p - o, dir), 0);
    auto tb = make_tuple(half(q - o, dir), (p - o).cross(q - o));
    if (ta != tb) {
      return ta < tb;
    }
    return ((p - o).sq() < (q - o).sq()) ^ inv;
  });
  if (inv) {
    reverse(P.begin(), P.end());
  }
}

template <class T>
using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll f(Point a, Point b, vector<Point>& P, bool inv = false) {
  Point dir = b - a;
  polarSortAround(a, dir, P, inv);

  oset<ll> oset;
  ll ret = 0;
  for (Point p : P) {
    T dot = dir.dot(p - a);
    int ord = int(oset.order_of_key(dot + inv));
    ret += ord;
    oset.insert(dot);
  }
  return ret;
}

ll gauss(int n) {
  return (ll)n * (n + 1) >> 1;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  Point s, e;
  s.read(), e.read();
  
  int n;
  cin >> n;

  vector<Point> P(n);
  for (Point& p : P) {
    p.read();
    p = p - s;
  }

  e = (e - s);
  s = (s - s);

  vector<int> inLine(2);
  vector<Point> L, R;
  for (Point& p : P) {
    T ori = orient(e, p);
    if (ori > 0) {
      L.push_back(p);
    } else if (ori < 0) {
      R.push_back(p);
    } else {
      ++inLine[e.dot(p) < 0];
    }
  }

  ll ans = gauss(inLine[0] - 1) + gauss(inLine[1] - 1) + f(s, e, L) + f(s, e, R, true) + f(e, s, L, true) + f(e, s, R);
  cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3712kb

input:

0 0 1 0
2
-1 0
2 0

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

0 0 1 0
4
-1 0
-2 0
2 0
3 0

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

0 0 2 0
3
1 1
2 2
2 1

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

0 0 2 0
3
1 1
0 2
0 1

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

5 0 6 0
10
8 0
3 0
2 0
11 0
4 0
9 0
0 0
10 0
7 0
1 0

output:

20

result:

ok single line: '20'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

0 0 1 0
3
1 1
1 2
1 3

output:

3

result:

ok single line: '3'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

0 0 4 3
2
5 0
3 0

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

0 0 4 3
2
3 0
5 0

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3456kb

input:

-1000000000 1000000000 1000000000 999999999
2
-1000000000 -1000000000
999999999 999999998

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

999999999 -1000000000 1000000000 999999999
2
-1000000000 -1000000000
999999999 999999998

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

999999997 999999999 -999999998 -999999998
6
999999999 999999998
1000000000 999999997
999999997 999999996
-999999997 -999999997
-999999999 -999999999
-1000000000 -1000000000

output:

5

result:

ok single line: '5'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

-1000000000 -1000000000 -999999999 -999999999
9
1000000000 1000000000
999999999 999999999
999999998 999999998
1000000000 999999999
999999999 999999998
999999998 999999997
999999999 1000000000
999999998 999999999
999999997 999999998

output:

3

result:

ok single line: '3'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

-3 -15 15 3
6
0 4
-4 0
-5 1
-1 5
-2 2
-3 3

output:

3

result:

ok single line: '3'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

-2 -8 8 2
5
-4 1
0 2
-3 0
-1 3
-2 4

output:

4

result:

ok single line: '4'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

1399 -1293 -2636 1822
1000
-510452 -660980
-126684 -163868
-71237 -92045
-2084 -2468
-443168 -573824
-499861 -647261
-222626 -288146
-421363 -545579
-238824 -309128
-115470 -149342
-267482 -346250
-355325 -460037
-273089 -353513
-7691 -9731
-28873 -37169
-63138 -81554
-92419 -119483
-463727 -600455
...

output:

499500

result:

ok single line: '499500'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3840kb

input:

2024 48517 -6336 -100443
2500
4054 -20413
25109 -48138
21969 -16503
11444 -46388
16584 -7353
16289 -47643
18964 -35013
9659 -25643
13579 -25863
-2496 -49538
43629 -33448
37804 -32138
26494 -5943
35944 -47763
5739 -25423
17104 -50638
39984 -28328
34369 -40793
19239 -30113
40789 -49018
5794 -24443
384...

output:

2514840

result:

ok single line: '2514840'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

350 2230 1241 -7802
1000
2224211 195148
1335173 114349
406676 32803
429557 33916
2330996 203713
73715 4150
709541 58783
878180 74680
2148596 187513
2700437 235606
1901525 164650
809699 69517
640229 52627
2005331 175708
185060 13120
454100 37015
1171925 99850
2173301 188788
1715315 149950
1357061 116...

output:

426462

result:

ok single line: '426462'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3968kb

input:

67176 -131382 -137128 265474
2500
-76892 101002
-36326 -5844
-67830 -30948
-63540 92326
-61326 16828
-156390 63408
-51544 86284
-23972 32726
-35526 1232
-160946 37738
-70122 51174
-53918 62848
-166448 54898
-170230 38512
-116262 106280
-91246 44742
-52920 15602
-36020 43184
-24538 5778
-93874 -32138...

output:

2511086

result:

ok single line: '2511086'

Test #19:

score: -100
Wrong Answer
time: 0ms
memory: 3840kb

input:

-247940590 -800864001 -376339814 357558744
1000
-381895428 -268441834
587795571 401546767
-233436735 -505362442
-769956233 -716358227
-35039180 789288175
886928299 -255208074
695681326 548764540
-435121059 -552564037
605862324 -706572950
-80805696 -171753153
-589436010 -269238096
110878492 781059697...

output:

91945

result:

wrong answer 1st lines differ - expected: '77951', found: '91945'