Untitled

tepyotin2

Jul 8th, 2023

Never

Add comment

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

C++ 5.19 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
/*
problem1: must find all xn = min(min(min(b.first, c.first), d.first), e.first) instead of xn = b.first; ...
problem2: use pair<int, int> c/e = listX[n - 1 - j] instead of listX[listX.size() - 1 - j]; so get 0,0 over array
problem3: forgot to valid same border
* no >> if ( xn < pv.first && pv.first < xx
&& yn < pv.second && pv.second < yx)
{
ok >> if ( xn < pv.first && pv.first < xx
&& yn < pv.second && pv.second < yx)
{
*/
bool isDiag = false;
vector<pair<int, int>> listV ;
int B = 4;
bool comp( pair<int, int>& a, pair<int, int>& b)
{
if ( a.second == b.second)
{
return a.first > b.first;
}
return a.second < b.second;
}
bool same(pair<int, int>& a, pair<int, int>& b){
return (a.first == b.first && a.second == b.second);
}
bool samePoint(pair<int, int>& a, pair<int, int>& b, pair<int, int>& c, pair<int, int>& d, pair<int, int>& e){
return same(a, b) || same(a, c) || same(a, d) || same(a, e);
//return (a.first == b.first && a.second == b.second)
//|| (a.first == c.first && a.second == c.second)
//|| (a.first == d.first && a.second == d.second)
//|| (a.first == e.first && a.second == e.second)
;
}
int main(){
//isDiag = true;
freopen("reduce.in", "r", stdin);
//freopen("reduce_silver_open16/2.in", "r", stdin);
int n;
cin >> n;
int x, y;
if(isDiag) cout << "n: " << n << endl;
for (int i = 0; i < n; i++)
{
cin >> x >> y;
listV.push_back({x, y});
}
sort(listV.begin(), listV.end());
vector<pair<int, int>> listX ;
vector<pair<int, int>> listY ;
//int loop = 0;
//pair<int, int> lastP = listV[0];
//for (int i = 1; i < n; i++)
//{
//pair<int, int> p = listV[i];
//if(p.first != lastP.first && p.second != lastP.second){
//listX.push_back(lastP);
//lastP = p;
//loop++;
//if (loop == B)
//{
//break;
//}
//}
//}
//loop = 0;
//lastP = listV[n-1];
//for (int i = 1; i < n; i++)
//{
//pair<int, int> p = listV[n-1-i];
//if(p.first != lastP.first && p.second != lastP.second){
//listX.push_back(lastP);
//lastP = p;
//loop++;
//if (loop == B)
//{
//break;
//}
//}
//}
for (int i = 0; i < B; i++)
{
listX.push_back(listV[i]);
listX.push_back(listV[n-i-1]);
}
sort(listV.begin(), listV.end(), comp);
//loop = 0;
//lastP = listV[0];
//for (int i = 1; i < n; i++)
//{
//pair<int, int> p = listV[i];
//if(p.first != lastP.first && p.second != lastP.second){
//listY.push_back(lastP);
//lastP = p;
//loop++;
//if (loop == B)
//{
//break;
//}
//}
//}
//loop = 0;
//lastP = listV[n-1];
//for (int i = 1; i < n; i++)
//{
//pair<int, int> p = listV[n-1-i];
//if(p.first != lastP.first && p.second != lastP.second){
//listY.push_back(lastP);
//lastP = p;
//loop++;
//if (loop == B)
//{
//break;
//}
//}
//}
for (int i = 0; i < B; i++)
{
listY.push_back(listV[i]);
listY.push_back(listV[n-i-1]);
}
sort(listX.begin(), listX.end());
sort(listY.begin(), listY.end(), comp);
if (isDiag)
{
for (int i = 0; i < listX.size(); i++)
{
cout << "x: " << listX[i].first << ", y: " << listX[i].second << endl;
}
for (int i = 0; i < listY.size(); i++)
{
cout << "y: " << listY[i].second << ", x: " << listY[i].first << endl;
}
}
int ans = INT_MAX;
int area = 0;
int xn, xx, yn, yx;
int loop = 0;
for (int i = 0; i < B; i++)
for (int j = 0; j < B; j++)
for (int k = 0; k < B; k++)
for (int l = 0; l < B; l++)
{
loop++;
pair<int, int> b = listX[i];
pair<int, int> c = listX[listX.size() - 1 - j];
pair<int, int> d = listY[k];
pair<int, int> e = listY[listY.size() - 1 - l];
//if (same(b, c) || same(b, d) || same(b, e)
//|| same(c, d) || same(c, e)
//|| same(d, e))
//{
//continue;
//}
//xn = b.first;
//xx = c.first;
//yn = d.second;
//yx = e.second;
xn = min(min(min(b.first, c.first), d.first), e.first);
xx = max(max(max(c.first, b.first), d.first), e.first);
yn = min(min(min(d.second, b.second), c.second), e.second);
yx = max(max(max(e.second, b.second), c.second), d.second);
if (isDiag) cout << "loop: " << loop<< ", xn: " << xn << ", xx: " << xx << ", yn: " << yn << ", yx: " << yx ;
if(isDiag && xn == 0) cout << " >>> b: " << b.first << ", " << b.second << ", c: " << c.first << ", " << c.second << ", d: " << d.first << ", " << d.second <<", e: " << e.first << ", " << e.second ;
int cnt = 0;
for (int i = 0; i < n; i++)
{
pair<int, int> pv = listV[i];
if ( xn <= pv.first && pv.first <= xx
&& yn <= pv.second && pv.second <= yx)
{
// within border
}else if (samePoint( pv, b, c, d, e))
{
// same
}
else
{
cnt++;
}
}
if(isDiag) cout << ", cnt: "<< cnt ;
if (cnt <= 3)
{
// valid
area = (xx - xn) * (yx - yn);
ans = min(ans, area);
if(isDiag) cout <<", area: " << area << ", ans: " << ans;
}
if (isDiag) cout << endl;
}
if (!isDiag) freopen("reduce.out", "w", stdout);
cout << ans << endl;
}

Add Comment

Please, Sign In to add comment