Pagini recente » Cod sursa (job #254904) | Cod sursa (job #265115) | Cod sursa (job #139283) | Cod sursa (job #254903) | Cod sursa (job #3275195)
#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;
}