Subtask ~1~ ~(1 \le n \le 100)~

• Sắp xếp các tọa độ theo thứ tự tăng dần, sau đó duyệt ~2~ biến ~L~ và ~R~ để tìm tất cả đoạn thẳng có thể.
• Với mỗi cặp ~L~, ~R~, ta đếm trên đoạn đó có đủ ~3~ màu hay không và cập nhật kết quả.
• Đpt: ~O(n^3 +n \times \log n)~.

Subtask ~2~ ~(1 \le n \le 1000)~

• Nhận thấy từ subtask ~1~, ta có thể kết hợp việc duyệt biến ~R~ với cập nhật kết quả, nên không cần duyệt lại đoạn ~[L, R]~.
• Đpt: ~O(n^2 +n \times \log n)~.

Code tham khảo

#include <bits/stdc++.h>
#define ll long long
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second

using namespace std;
typedef pair<int, int> ii;

int n;
vector<ii>a;

int main()
{
    freopen("PPOINT.INP", "r", stdin);
    freopen("PPOINT.OUT", "w", stdout);
    cin>>n;
    for(int i = 0; i<n; i++)
    {
        ii x; cin>>x.fi>>x.se;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    int ans = 1e9;
    for(int i = 0; i<n-1; i++)
    {
        int cnt[4];
        memset(cnt, 0, sizeof(cnt));
        cnt[a[i].se]++;
        for(int j = i+1; j<n; j++)
        {
            cnt[a[j].se]++;
            if (cnt[1] && cnt[2] && cnt[3]){
                ans = min(ans, a[j].fi - a[i].fi);
                break;
            }
        }
    }
    if (ans == 1e9) cout<<-1;
    else cout<<ans;
    return 0;
}

Subtask ~3~ ~(1 \le n \le 10^6)~

• Dựa vào subtask ~2~, ta áp dụng thêm kĩ thuật hai con trỏ để tối ưu thuật toán.
• Đpt: ~O(n + n \times \log n)~.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;


typedef pair<int, int> ii;
#define fi first
#define se second

int n, cnt[4];
vector<ii>a;

int main()
{
    freopen("PPOINT.INP", "r", stdin);
    freopen("PPOINT.OUT", "w", stdout);
    cin>>n;
    for(int i = 0; i<n; i++)
    {
        ii x; cin>>x.fi>>x.se;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    int ans = 1e9;

    int l = 0, r = 0;
    while(r < n)
    {
        cnt[a[r].se]++;
        while(cnt[1] && cnt[2] && cnt[3])
        {
            ans = min(ans, a[r].fi - a[l].fi);
            cnt[a[l].se]--;
            l++;
        }
        r++;
    }

    if (ans == 1e9) cout<<-1;
    else cout<<ans;
    return 0;
}