QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#747095#9520. Concave Hullucup-team3702#WA 1ms3632kbC++143.5kb2024-11-14 16:19:392024-11-14 16:19:45

Judging History

你现在查看的是最新测评结果

  • [2024-11-14 16:19:45]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3632kb
  • [2024-11-14 16:19:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i, d, u) for(int i = d; i <= u; ++i)
#define cep(n) while(n--)
const int _maxn = 100011;
struct node {
	int xa, ya;
} nods[_maxn];
long long calc(node le, node ri, node mi) {
	return 1ll * (le . xa - mi . xa) * (ri . ya - mi . ya) - 1ll * (ri . xa - mi . xa) * (le . ya - mi . ya);
}
long long mabs(long long da) {
	return da < 0 ? -da : da;
}
void dmin(long long &le, long long ri) {
	if(le > ri) {
		le = ri;
	}
}
int t, n, latp, ratp, poin;
bool pdif[_maxn];
long long rans, dans;
vector<int> uatp, datp;
vector<node> usta, dsta, idot, udox, ddox;
int main() {
	cin >> t;
	cep(t) {
		cin >> n, rans = 0;
		rep(i, 1, n) {
			cin >> nods[i] . xa >> nods[i] . ya, pdif[i] = 0;
		}
		sort(nods + 1, nods + n + 1, [](node le, node ri) {
			return le . xa == ri . xa ? le . ya < ri . ya : le . xa < ri . xa;
		});
		if(nods[1] . xa == nods[n] . xa) {
			puts("-1");
			continue;
		}
		for(latp = 1; nods[1] . xa == nods[latp + 1] . xa && latp + 1 <= n; ) {
			++latp;
		}
		for(ratp = n; nods[n] . xa == nods[ratp - 1] . xa && ratp - 1 >= 1; ) {
			--ratp;
		}
		usta . clear(), usta . push_back(nods[latp]);
		rep(i, latp + 1, ratp) {
			while(usta . size() >= 2 && calc(usta . back(), nods[i], usta[usta . size() - 2]) < 0) {
				usta . pop_back(), uatp . pop_back();
			}
			usta . push_back(nods[i]), uatp . push_back(i);
		}
		rep(i, ratp + 1, n) {
			usta . push_back(nods[i]);
		}
		dsta . clear();
		rep(i, 1, latp) {
			dsta . push_back(nods[i]);
		}
		rep(i, latp + 1, ratp - 1) {
			while(dsta . size() >= 2 && calc(dsta . back(), nods[i], dsta[dsta . size() - 2]) > 0) {
				dsta . pop_back(), datp . pop_back();
			}
			dsta . push_back(nods[i]), datp . push_back(i);
		}
		while(dsta . size() >= 2 && calc(dsta . back(), nods[n], dsta[dsta . size() - 2]) > 0) {
			dsta . pop_back(), datp . pop_back();
		}
		dsta . push_back(nods[n]), datp . push_back(n);

		for(int i : uatp) {
			pdif[i] = 1;
		}
		for(int i : datp) {
			pdif[i] = 1;
		}
		idot . clear();
		rep(i, latp + 1, ratp - 1) {
			if(!pdif[i]) {
				idot . push_back(nods[i]);
			}
		}
		if(idot . empty()) {
			puts("-1");
			continue;
		}
		sort(idot . begin(), idot . end(), [](node le, node ri) {
			return le . xa == ri . xa ? le . ya < ri . ya : le . xa < ri . xa;
		}), udox . clear(), ddox . clear();
		for(node i : idot) {
			while(udox . size() >= 2 && calc(udox . back(), i, udox[udox . size() - 2]) < 0) {
				udox . pop_back();
			}
			udox . push_back(i);
		}
		for(node i : idot) {
			while(ddox . size() >= 2 && calc(ddox . back(), i, ddox[ddox . size() - 2]) > 0) {
				ddox . pop_back();
			}
			ddox . push_back(i);
		}
		poin = 0;
		rep(i, 0, usta . size() - 2) {
			rans += mabs(calc(usta[i], usta[i + 1], nods[1]));
		}
		rep(i, 0, dsta . size() - 2) {
			rans += mabs(calc(dsta[i], dsta[i + 1], nods[1]));
		}
		dans = rans, poin = 0;
		rep(i, 0, usta . size() - 2) {
			while(poin + 1 < udox . size() &&
			mabs(calc(udox[poin], usta[i], usta[i + 1])) > mabs(calc(udox[poin + 1], usta[i], usta[i + 1]))) {
				++poin;
			}
			dmin(dans, mabs(calc(udox[poin], usta[i], usta[i + 1])));
		}
		poin = 0;
		rep(i, 0, dsta . size() - 2) {
			while(poin + 1 < ddox . size() &&
			mabs(calc(ddox[poin], dsta[i], dsta[i + 1])) > mabs(calc(ddox[poin + 1], dsta[i], dsta[i + 1]))) {
				++poin;
			}
			dmin(dans, mabs(calc(ddox[poin], dsta[i], dsta[i + 1])));
		}
		cout << rans - dans << endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3552kb

input:

2
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1

output:

40
-1

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3632kb

input:

10
243
-494423502 -591557038
-493438474 -648991734
-493289308 -656152126
-491185085 -661710614
-489063449 -666925265
-464265894 -709944049
-447472922 -737242534
-415977509 -773788538
-394263365 -797285016
-382728841 -807396819
-373481975 -814685302
-368242265 -818267002
-344482838 -833805545
-279398...

output:

2178418010787347715
1826368028392114576
1651576777857324182
-1
2117508968210834312
-1
2271187626637934107
1998603021688424104
-1
1167075593052552142

result:

wrong answer 2nd lines differ - expected: '1826413114144932145', found: '1826368028392114576'