Problem Info
Link: USACO
My Work
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct Cow {
int x;
int y;
};
bool cmpy(Cow a, Cow b) {
if (a.y == b.y) {
return a.x < b.x;
}
else {
return a.y < b.y;
}
}
bool cmpx(Cow a, Cow b) {
if (a.x == b.x) {
return a.y < b.y;
}
else {
return a.x < b.x;
}
}
int main() {
ifstream fin("reduce.in");
ofstream fout("reduce.out");
int N;
fin >> N;
Cow c[50000];
int a;
for (a = 0; a < N; a++) {
fin >> c[a].x;
fin >> c[a].y;
}
Cow r[12];
int p = 0;
Cow g;
g.x = -1;
g.y = -1;
sort(c, c + N, cmpx);
int i;
for (i = 0; i < 3; i++) {
r[i] = c[i];
}
r[3] = c[N - 3];
r[4] = c[N - 2];
r[5] = c[N - 1];
sort(c, c + N, cmpy);
int j;
bool v = true;
for (i = 0; i < 3; i++) {
v = true;
for (j = 0; j < 6; j++) {
if (c[i].x == r[j].x && c[i].y == r[j].y) {
v = false;
}
}
if (v == true) {
r[i + 6] = c[i];
}
else {
r[i + 6] = g;
}
}
for (j = 0; j < 6; j++) {
v = true;
if (c[N - 3].x == r[j].x && c[N - 3].y == r[j].y) {
v = false;
}
}
if (v == true) {
r[9] = c[N - 3];
}
else {
r[9] = g;
}
for (j = 0; j < 6; j++) {
v = true;
if (c[N - 2].x == r[j].x && c[N - 2].y == r[j].y) {
v = false;
}
}
if (v == true) {
r[10] = c[N - 2];
}
else {
r[10] = g;
}
for (j = 0; j < 6; j++) {
v = true;
if (c[N - 1].x == r[j].x && c[N - 1].y == r[j].y) {
v = false;
}
}
if (v == true) {
r[11] = c[N - 1];
}
else {
r[11] = g;
}
int k;
int f = 1600000000;
int z;
int minx;
int maxx;
int miny;
int maxy;
bool v1;
bool v2;
bool v3;
bool v4;
int area;
for (i = 0; i < 10; i++) {
for (j = i + 1; j < 12; j++) {
for (k = i + 2; k < 12; k++) {
if (r[i].x != -1 && r[j].x != -1 && r[k].x != -1) {
v1 = false;
v2 = false;
v3 = false;
v4 = false;
sort(c, c + N, cmpx);
z = 0;
while(z < N) {
if (c[z].x != r[i].x || c[z].y != r[i].y) {
if (c[z].x != r[j].x || c[z].y != r[j].y) {
if (c[z].x != r[k].x || c[z].y != r[k].y) {
minx = c[z].x;
v1 = true;
z = N - 1;
}
}
}
z++;
}
while(z >= 0) {
z--;
if (c[z].x != r[i].x || c[z].y != r[i].y) {
if (c[z].x != r[j].x || c[z].y != r[j].y) {
if (c[z].x != r[k].x || c[z].y != r[k].y) {
maxx = c[z].x;
v2 = true;
z = -1;
}
}
}
}
sort(c, c + N, cmpy);
while (z < N) {
z++;
if (c[z].x != r[i].x || c[z].y != r[i].y) {
if (c[z].x != r[j].x || c[z].y != r[j].y) {
if (c[z].x != r[k].x || c[z].y != r[k].y) {
miny = c[z].y;
v3 = true;
z = N;
}
}
}
}
while (z >= 0) {
z--;
if (c[z].x != r[i].x || c[z].y != r[i].y) {
if (c[z].x != r[j].x || c[z].y != r[j].y) {
if (c[z].x != r[k].x || c[z].y != r[k].y) {
maxy = c[z].y;
v4 = true;
z = -1;
}
}
}
}
if (v1 == true && v2 == true && v3 == true && v4 == true) {
area = (maxx - minx) * (maxy - miny);
f = min(f, area);
}
}
}
}
}
fout << f;
}
My code essentially generates a list of points that either have the 3 least x or y coordinates or the 3 most x or y coordinates. Then, it cycles through these points, choosing 3 at a time. It then finds the least x and y and greatest x and y excluding these points. It uses the results to calculate the area. Then it takes the minimum.
Note: I chose not to comment my code further than this, since I do not need help on the algorithm and such. This should be enough to read my code well enough to determine time complexity. Let me know if I need to comment further or elaborate.
## What I have Tried
I've tried looking at the test data.
## Question
Currently, I've got 8/10 test cases. I'm timing out on the 9th and 10th. However, I calculated the time complexity and I believe I should still make it. though it was a rough estimate. Therefore, I have two questions. One: What is the time complexity of my program and what does it need to be (roughly) to run in time? Two: Is there anything I can do to make my program run faster?