NC24296. [USACO 2016 Ope B]Field Reduction
描述
输入描述
The first line of input contains N. The next N lines each contain two integers specifying the location of a cow. Cow locations are positive integers in the range 1…40,000.
输出描述
Write a single integer specifying the minimum area FJ can enclose with his fence after removing one carefully-chosen cow from his herd.
示例1
输入:
4 2 4 1 1 5 2 17 25
输出:
12
C++14(g++5.4) 解法, 执行用时: 44ms, 内存消耗: 864K, 提交时间: 2020-08-05 10:31:51
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#include <emmintrin.h>
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#define vi vector<int>
#define pii pair<int, int >
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define LL long long
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define all(x) (x).begin(), (x).end()
#define all2(x,n) (x+1), (x+1+n)
#define sz(x) ((int)(x).size())
#define mod(x) ((x)%MOD)
#define debug(x) cerr<<#x<<" : "<<x<<endl
#define mt make_tuple
#define eb emplace_back
#define o(X) (1<<(X))
#define oL(X) (1LL<<(X))
#define contain(S,X) (((S)&o(X))!=0)
#define containL(S,X) (((S)&oL(X))!=0)
using namespace std;
const int INF=0x3f3f3f3f,N=4e6+5,MOD=998244353;
const LL INF_LL=0x3f3f3f3f3f3f3f3fLL;
inline int getplc(int x,int y) { return (x>>y)&1; }
template<typename T>
T square(T x) {return x*x;}
LL qpow(LL a,LL b=MOD-2,LL _MOD=MOD){
LL res=1;
for(;b;b>>=1,a=a*a%_MOD){
if(b&1)res=res*a%_MOD;
}
return res;
}
// Smax
//int Smax() { return -INF; }
template <typename T>
T Smax(T x) { return x; }
template<typename T, typename... Args>
T Smax(T a, Args... args) { return max(a, Smax(args...)); }
// Smin
template <typename T>
T Smin(T x) { return x; }
template<typename T, typename... Args>
T Smin(T a, Args... args) { return min(a, Smin(args...)); }
template <typename T>
// erro
#define errorl(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); errl(_it, args); }
void errl(istream_iterator<string> it) {}
template<typename T, typename... Args>
void errl(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << endl;
errl(++it, args...);
}
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cerr<<endl;}
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << "=" << a << " # ";
err(++it, args...);
}
void Solve();
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
// freopen("o1.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
Solve();
return 0;
}
// ---------------------------start------------------------------
struct node{
int x,y,id;
};
node a[N];
void Solve(){
int n;
cin>>n;
rep(i,1,n){
cin>>a[i].x>>a[i].y;
a[i].id=i;
}
set<int>st;
sort(a+1,a+1+n,[&](node a,node b){return a.x<b.x;});
rep(i,1,3)st.insert(a[i].id);
sort(a+1,a+1+n,[&](node a,node b){return a.x>b.x;});
rep(i,1,3)st.insert(a[i].id);
sort(a+1,a+1+n,[&](node a,node b){return a.y<b.y;});
rep(i,1,3)st.insert(a[i].id);
sort(a+1,a+1+n,[&](node a,node b){return a.y>b.y;});
rep(i,1,3)st.insert(a[i].id);
LL ans=INF_LL;
vi lst;
for(auto p:st)lst.pb(p);
rep(i,0,sz(lst)-1){
int maxnx=0,maxny=0,minnx=INF,minny=INF;
rep(p,1,n)
if(a[p].id!=lst[i]){
minnx=min(minnx,a[p].x);
minny=min(minny,a[p].y);
maxnx=max(maxnx,a[p].x);
maxny=max(maxny,a[p].y);
}
ans=min(ans,(LL)(maxnx-minnx)*(maxny-minny));
}
cout<<ans<<endl;
}
Java(javac 1.8) 解法, 执行用时: 826ms, 内存消耗: 94668K, 提交时间: 2020-08-05 09:01:29
import java.util.*;
public class Main {
public static long getAreas(int n, int[][] a) {
long s1 = areas(n, a);
int[][] b = new int[n][2];
for (int i = 0; i < n; i++) {
b[i][0] = a[i][1];
b[i][1] = a[i][0];
}
long s2 = areas(n, b);
return Math.min(s1, s2);
}
public static long areas(int n, int[][] a) {
Arrays.sort(a, (a1, a2) -> a1[0] - a2[0]);
int y_max = a[1][1], y_min = a[1][1];
for (int i = 2; i < n - 1; i++) {
if (a[i][1] > y_max) y_max = a[i][1];
if (a[i][1] < y_min) y_min = a[i][1];
}
int y_max1 = Math.max(y_max, a[0][1]);
int y_min1 = Math.min(y_min, a[0][1]);
int y_maxn = Math.max(y_max, a[n - 1][1]);
int y_minn = Math.min(y_min, a[n - 1][1]);
long s1 = ((long) (y_max1 - y_min1)) * (a[n - 2][0] - a[0][0]);
long sn = ((long) (y_maxn - y_minn)) * (a[n - 1][0] - a[1][0]);
return Math.min(s1, sn);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n;
int[][] a;
n = sc.nextInt();
a = new int[n][2];
for (int i = 0; i < n; i++) {
a[i][0] = sc.nextInt();
a[i][1] = sc.nextInt();
}
sc.close();
System.out.println(getAreas(n, a));
}
}
C++11(clang++ 3.9) 解法, 执行用时: 20ms, 内存消耗: 1276K, 提交时间: 2020-08-07 12:44:04
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> P;
const int maxn=1e6+5;
int m,n,k;
P A[500005];
bool cmp(const P&a ,const P&b){
return a.y < b.y;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d%d",&A[i].x,&A[i].y);
sort(A,A+n);
ll w=A[n-1].x-A[1].x;
ll h=(*max_element(A+1,A+n,cmp)).y - (*min_element(A+1,A+n,cmp)).y;
ll ans=w*h;
w=A[n-2].x-A[0].x;
h=(*max_element(A,A+n-1,cmp)).y - (*min_element(A,A+n-1,cmp)).y;
ans=min(ans,w*h);
sort(A,A+n,cmp);
h=A[n-2].y-A[0].y;
w=(*max_element(A,A+n-1)).x - (*min_element(A,A+n-1)).x;
ans=min(ans,w*h);
h=A[n-1].y-A[1].y;
w=(*max_element(A+1,A+n)).x - (*min_element(A+1,A+n)).x;
ans=min(ans,w*h);
cout<<ans;
return 0;
}