Farm Enclosure

tepyotin2

Jan 17th, 2024

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 5.02 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
struct Points{
int x;
int y;
int idx;
Points(){};
Points(int x1, int y1, int idx1){
x = x1;
y = y1;
idx = idx1;
};
};
int n;
int sx(Points a, Points b){
if(a.x != b.x){
return a.x > b.x;
}else{
return a.y > b.y;
}
}
int sy(Points a, Points b){
if(a.y != b.y){
return a.y > b.y;
}else{
return a.x > b.x;
}
}
int main(){
ios_base::sync_with_stdio(0), cin.tie(0);
// freopen("fenclosure.in", "r", stdin);
cin >> n;
int a, b;
int mid_left = n/2;
// cout << mid_left << '\n';
int mid_right = mid_left;
if(n%2 == 1){
mid_right = mid_left+1;
}
// cout << mid_right << '\n';
Points point[n];
for(int i=0; i<n; i++){
cin >> a >> b;
point[i].x = a;
point[i].y = b;
point[i].idx = i+1;
}
sort(point, point+n, sx);
for(int i=0; i<n; i++){
// cout << "i: " << i << ", pos: " << point[i].idx << ", x: " << point[i].x << ", y: " << point[i].y << '\n';
}
int one = 0;
int two = 0;
int three = 0;
int four = 0;
int val = 0;
int mid_left1 = mid_left;
int mid_left2 = mid_left;
int mid_right1 = mid_right;
int mid_right2 = mid_right;
vector<Points> mx_x;
mx_x.push_back(Points(point[0].x, point[0].y, point[0].idx));
one++;
// cout << mx_x[0].x << ", " << mx_x[0].y << '\n';
for(int i=1; i<mid_left1; i++){
if(val >= 3 && point[i].x != point[0].x){
// cout << "val: " << val << ", point[i].x: " << point[i].x << ", point[0].x: " << point[0].x << '\n';
break;
}
if(val>=3 && point[i].x == point[0].x){
mid_left1++;
}
val++;
one++;
mx_x.push_back(Points(point[i].x, point[i].y, point[i].idx));
// cout << "mx_x[i].x: " << mx_x[i].x << ", mx_x[i].y: " << mx_x[i].y << '\n';
}
val = 0;
int val_2 = 0;
vector<Points> mn_x;
mn_x.push_back(Points(point[n-1].x, point[n-1].y, point[n-1].idx));
two++;
// cout << mn_x[0].x << ", " << mn_x[0].y << '\n';
for(int i=n-2; i>=mid_right1; i--){
if(val >= 3 && point[i].x != point[n-1].x){
break;
}
if(val>=3 && point[i].x == point[n-1].x){
mid_right1--;
}
val++;
two++;
mn_x.push_back(Points(point[i].x, point[i].y, point[i].idx));
// cout << "i: " << i << ", mn_x[i].x: " << mn_x[val_2].x << ", mn_x[i].y: " << mn_x[val_2].y << '\n';
val_2++;
}
val = 0;
sort(point, point+n, sy);
vector<Points> mx_y;
mx_y.push_back(Points(point[0].x, point[0].y, point[0].idx));
three++;
// cout << mx_y[0].x << ", " << mx_y[0].y << '\n';
for(int i=1; i<mid_left2; i++){
if(val >= 3 && point[i].y != point[0].y){
break;
}
if(val>=3 && point[i].y == point[0].y){
mid_left2++;
}
val++;
three++;
mx_y.push_back(Points(point[i].x, point[i].y, point[i].idx));
// cout << "mx_y[i].x: " << mx_y[i].x << ", mx_y[i].y: " << mx_y[i].y << '\n';
}
val = 0;
val_2 = 0;
vector<Points> mn_y;
mn_y.push_back(Points(point[n-1].x, point[n-1].y, point[n-1].idx));
four++;
// cout << mn_y[0].x << ", " << mn_y[0].y << '\n';
for(int i=n-2; i>=mid_right2; i--){
if(val >= 3 && point[i].y != point[n-1].y){
break;
}
if(val>=3 && point[i].y == point[n-1].y){
mid_right2++;
}
val++;
four++;
mn_y.push_back(Points(point[i].x, point[i].y, point[i].idx));
// cout << "mn_y[i].x: " << mn_y[val_2].x << ", mn_y[i].y: " << mn_y[val_2].y << '\n';
val_2++;
}
// cout << "one: " << one << '\n';
// cout << "two: " << two << '\n';
// cout << "three: " << three << '\n';
// cout << "four: " << four << '\n';
int count = 0;
int area = 0;
int ans = INT_MAX;
for(int a=0; a<one; a++){
for(int b=0; b<two; b++){
for(int c=0; c<three; c++){
for(int d=0; d<four; d++){
count = 0;
for(int i=0; i<n; i++){
if(point[i].x > mx_x[a].x || point[i].x < mn_x[b].x || point[i].y > mx_y[c].y || point[i].y < mn_y[d].y){
count++;
}
}
// cout << "count: " << count << '\n';
if(count<=3){
area = (mx_x[a].x - mn_x[b].x) * (mx_y[c].y - mn_y[d].y);
// cout << "area: " << area << ", mx_x: " << mx_x[a].x << ", mn_x: " << mn_x[b].x << ", mx_y: " << mx_y[c].y << ", mn_y: " << mn_y[d].y << '\n';
ans = min(area, ans);
}
}
}
}
}
cout << ans << '\n';
}

Add Comment

Please, Sign In to add comment