Cod sursa(job #3275195)

Utilizator uncle_sam_007ioan bulik uncle_sam_007 Data 9 februarie 2025 13:56:16
Problema Subsecventa de suma maxima Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.2 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("supertri.in");
ofstream fout("supertri.out");

const int NMAX = 301;

int n;

int dp[NMAX][NMAX]; // dp[i][j] = nr de puncte situate in trapezul determinat de
                    //            axa Ox si puncte i si j
struct Point{
    int x, y;
};

Point p[NMAX];

int det(Point A, Point B, Point C){
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

int ccw(Point A, Point B, Point C){
    int cp = det(A, B, C);
    if(cp == 0){
        return 0;
    }
    if(cp > 0){
        return 1; // sens trigonometric
    }
    return -1;
}


void solve(){
    fin >> n;
    for(int i = 1; i <= n; ++i){
        fin >> p[i].x >> p[i].y;
    }
    for(int i = 1; i < n; ++i){
        for(int j = i + 1; j <= n; ++j){
            for(int k = 1; k <= n; ++k){
                if(p[i].x == p[j].x && p[k].y <= max(p[i].y, p[j].y))
                        dp[i][j] ++;
                if(p[i].x != p[j].x && ccw(p[i], p[j], p[k]) <= 0 && i != k && j != k && min(p[i].x, p[j].x) <= p[k].x && max(p[i].x, p[j].x) >= p[k].x){
                        dp[i][j] ++;

                }
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            fout << dp[i][j] << " ";
        }
        fout << "\n";
    }
    int p1, p2, p3;
    int mx = 0;
    for(int i = 1; i < n; ++i){
        for(int j = i + 1; j <= n; ++j){
            for(int k = 1; k <= n; ++k){
                if((mx < dp[i][j] + dp[j][k] - dp[i][k] && i != k && j != k && i != j)){
                    mx = dp[i][j] + dp[j][k] - dp[i][k];
                    p1 = i;
                    p2 = j;
                    p3 = k;
                }
                else{
                    if((mx < dp[j][i] + dp[k][j] - dp[k][i] && i != k && j != k && i != j)){
                    mx = dp[j][i] + dp[k][j] - dp[k][i];
                    p1 = i;
                    p2 = j;
                    p3 = k;
                }
                }
            }
        }
    }
    fout << mx << "\n" << p1 << " " << p2 << " " << p3;

}

int main()
{
    solve();
    return 0;
}