ในข้อนี้ เราต้องการขับรถผ่านบีคอนให้มากที่สุด โดยรถจะเลี้ยวขวาได้เท่านั้น และห้ามเลี้ยวเกิน $270^{\circ}$

กำหนดให้เส้นตรง $L$ เป็นเส้นตรงที่ลากผ่านจุด $(0, 0)$ และ $(A, A)$ เราจะสามารถแบ่งบีคอนออกเป็น 3 ประเภทได้แก่ บีคอนที่อยู่เหนือ $L$, บีคอนที่อยู่บน $L$ และบีคอนที่อยู่ใต้ $L$ จะขอเรียกว่าประเภทที่ 1, 2 และ 3 ตามลำดับ สังเกตว่าสำหรับการขับรถขาไปจะเลี้ยวรถได้แค่ $90^{\circ}$ เท่านั้น จึงทำให้เราจะไม่สามารถขับรถเพื่อไปเก็บจากบีคอนประเภทที่ 2 และ 3 ได้ เมื่อผ่านบีคอนประเภทที่ 2 หรือ 3 แล้ว จะไม่สามารถไปถึงพิกัด $(A, A)$ ได้

ข้อสังเกตอีกอย่างคือ หากเราขับรถผ่านบีคอนประเภทที่ 2 เราจะไม่สามารถเลี้ยวได้อีกเพราะจะทำให้ไม่สามารถไปถึงพิกัด $(A, A)$ ได้ ดังนั้นจึงต้องขับรถตามเส้นตรง $L$ ตลอดจนกว่าจะถึงพิกัด $(A, A)$ จึงสรุปได้ว่าในการขับรถทั้งขาไปและขากลับ จะเลือกเก็บบีคอนได้เพียง 1 ประเภทเท่านั้น

จากข้อสังเกตเหล่านี้ เราจึงสรุปได้ว่าในการขับรถขาไป เราจะสามารถขับผ่านบีคอนได้แค่บีคอนประเภทที่ 1 และ 2 เท่านั้น และในทำนองเดียวกัน สำหรับการขับรถขากลับ ก็จะผ่านบีคอนประเภทที่ 2 และ 3 ได้เท่านั้นเช่นกัน

กำหนดให้ $ans_1$, $ans_2$ และ $ans_3$ แทนแต้มที่มากที่สุดที่ได้จากการขับรถผ่านบีคอนประเภทที่ 1, 2 และ 3 ตามลำดับ โดย $ans_1$ จะพิจารณาการขับรถขาไปเท่านั้น และ $ans_3$ จะพิจารณาการขับรถขากลับเท่านั้นเช่นกัน เราจะสามารถสรุปได้ทันทีว่า $ans_2$ เท่ากับจำนวนบีคอนประเภทที่ 2 เพราะเราสามารถขับผ่านทุกบีคอนประภทที่ 2 ได้ ดังนั้นจึงเหลือ $ans_1$ และ $ans_3$ ที่จะต้องมาคำนวณ ซึ่งจะขออธิบายวิธีการคำนวณ $ans_1$ เท่านั้น เนื่องจากวิธีการคำนวณ $ans_3$ มีความคล้ายลึงกันมาก

กำหนดให้เซตของพิกัด $S = \{(0, 0), B_1, B_2, B_3, ..., B_k, (A, A)\}$ เมื่อ $B_i$ คือพิกัดของบีคอนประเภทที่ 1 ลำดับที่ $i$ และ $k$ คือจำนวนบีคอนประเภทที่ 1 และ $S_i$ แทนสมาชิกของ $S$ ตัวที่ $i$ เราจะทำการหา $ans_1$ ด้วยการใช้ Dynamic Programming ดังนี้ กำหนดให้ $dp(i)$ แทนแต้มที่มากที่สุดที่ได้จากการขับรถมาจนถึงพิกัด $S_i$ พิจารณาพิกัด $S_i$ และ $S_j$ ใด ๆ ถ้า $dp(j) + 1 \geq dp(i)$ และรถจะเลี้ยวขวาเมื่อขับจาก $S_j$ มา $S_i$ จะแก้ไขให้ $dp(i) := dp(j) + 1$ แต่เนื่องจากหากเรานิยาม $dp(i)$ ตามนี้แล้ว เราจะไม่สามารถทราบได้ว่าการขับรถจาก $S_j$ มา $S_i$ เลี้ยวขวาหรือไม่

ดังนั้น เราจะพิจารณาพิกัด $S_i$ และ $S_j$ ตามความชันของเส้นตรงที่ลากผ่านสองจุดนี้ซึ่งแทนองศาของรถขณะขับผ่านทั้งสองจุด จากมากไปน้อย เพื่อรับประกันว่า การขับรถจาก $S_j$ มา $S_i$ จะเลี้ยวขวาเสมอ โดยเราจะสนใจ $S_i$ และ $S_j$ ที่ความชันของเส้นตรงที่ลากผ่านสองจุดนี้อยู่ในช่วง $[0, \infty)$ เนื่องจากรถสามารถเลี้ยวได้เพียง $90^{\circ}$ ดังที่ได้กล่าวไว้ในย่อหน้าที่ 2

ในตอนแรก เราจะกำหนดให้ $dp(1) := 1$ และ $dp(i) := -1$ สำหรับ $2 \leq i \leq |S|$ เพื่อแสดงว่า $dp(i)$ ยังไม่ได้นับการคำนวณหากมีค่าเท่ากับ $-1$ และเมื่อคำนวณค่า $dp(i)$ เป็นที่เรียบร้อยแล้ว เราจะได้ว่า $ans_1 = dp(|S|) - 2$ เนื่องจากพิกัด $(A, A)$ เป็นสมาชิกลำดับที่ $|S|$ ของ $S$ และต้องลบ 2 ออกจาก $ans_1$ เพราะได้นับแต้มรวมพิกัด $(0, 0)$ และ $(A, A)$ ด้วย

หลังจากทราบค่า $ans_1$, $ans_2$ และ $ans_3$ เป็นที่เรียบร้อยแล้ว คำตอบของข้อนี้คือ $\max(ans_1 + ans_2, ans_2 + ans_3, ans_1 + ans3)$ ซึ่งมาจากการที่เราสามารถขับผ่านบีคอนประเภทที่ 2 ได้อย่างมาก 1 ครั้ง

โค้ดตัวอย่างดังนี้

#include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5;

double slope(pair<int, int> a,
             pair<int, int> b) { // Function for caculating slope given 2 points
  if (a.first == b.first)
    return 1e9;
  return (double)(a.second - b.second) / (double)(a.first - b.first);
}

int solve(vector<pair<int, int>> &V) { // Function for caculating ans_1 and
                                       // ans_3
  int sz = V.size();
  vector<pair<int, int>> line;
  for (int i = 0; i < sz; i++)
    for (int j = 0; j < i; j++) {
      if (slope(V[i], V[j]) < 0)
        continue;
      line.emplace_back(i, j);
    }
  sort(line.begin(), line.end(),
       [&](const pair<int, int> &a,
           const pair<int, int> &b) { // Sort by slope in descending order
         double m1 = slope(V[a.first], V[a.second]);
         double m2 = slope(V[b.first], V[b.second]);
         return m1 > m2;
       });
  int dp[N];
  memset(dp, -1, sizeof dp);
  dp[0] = 1; // Base case
  for (pair<int, int> l : line) // Dynamic Programming
    if (dp[l.second] != -1)
      dp[l.first] = max(dp[l.first], dp[l.second] + 1);
  return dp[sz - 1] - 2;
}

int A, n, diag;
vector<pair<int, int>> hi, lo;

int main() {
  scanf("%d %d", &A, &n);
  for (int i = 1, a, b; i <= n; i++) {
    scanf("%d %d", &a, &b);
    if (a == b)
      ++diag;
    else if (a < b)
      hi.emplace_back(a, b);
    else
      lo.emplace_back(A - a, A - b);
  }
  hi.emplace_back(0, 0), hi.emplace_back(A, A);
  lo.emplace_back(0, 0), lo.emplace_back(A, A);
  sort(hi.begin(), hi.end()), sort(lo.begin(), lo.end());
  int high = solve(hi), low = solve(lo);
  printf("%d\n", max({high + low, high + diag, diag + low}));

  return 0;
}

Time Complexity: $\mathcal{O}(N^2 \log N)$