Museum

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef double ld;
typedef long long ll;
ld cp(pair<ld, ld> x, pair<ld, ld> y) {
	return x.F*y.S - y.F*x.S;
}
ld le, wi;
ld x, y, ws;
pair<ld, ld> getPos(ld q) {
	if(q < le) return {0, q};
	q -= le;
	if(q < wi) return {q, le};
	q -= wi;
	if(q < le) return {wi, le-q};
	q -= le;
	if(q < wi) return {wi-q, 0};
	cout<<"BUGI"<<endl;;
	while(1);
}
bool coll(pair<ld, ld> a, pair<ld, ld> b, pair<ld, ld> c, pair<ld, ld> d) {
//	cout<<"coll "<<a.F<<' '<<a.S<<"   " <<b.F<<" "<<b.S<<"   "<<c.F<<' '<<c.S<<"   "<<d.F<<' '<<d.S<<'\n';
	pair<ld, ld>  ba = {a.F-b.F, a.S-b.S};
	pair<ld, ld> cb = {c.F-b.F, c.S-b.S};
	pair<ld, ld> db = {d.F-b.F, d.S-b.S};
	if(cp(ba, cb)*cp(ba, db) > 0) {
//		cout<<"ei leikkaa\n";
		return 0;
	}
	pair<ld, ld> dc = {d.F-c.F, d.S-c.S};
	pair<ld, ld> ad = {a.F-d.F, a.S-d.S};
	pair<ld, ld> bd = {b.F-d.F, b.S-d.S};
	if(cp(dc, ad)*cp(dc, bd) > 0) {
//		cout<<"ei leikkaa\n";
		return 0;
	}
//	cout<<"leikkaa\n";
	return 1;
}

bool check(pair<ld, ld> t[3], pair<ld, ld> p[4]) {
	for(int i = 0; i < 3; ++i) {
		for(int j = i+1; j < 3; ++j) {
			if(coll(t[i], t[j], p[0], p[1])) return 0;
			if(coll(t[i], t[j], p[0], p[2])) return 0;
			if(coll(t[i], t[j], p[3], p[1])) return 0;
			if(coll(t[i], t[j], p[3], p[2])) return 0;
		}
	}
	return 1;
}
ll bs[444][10];
ll side[5][10];
void solve() {
	memset(bs, 0, sizeof bs);
	memset(side, 0, sizeof side);
	cin>>le>>wi;
	ld x, y, w;
	cin>>y>>x>>w;
	pair<ld, ld> t[3];
	pair<ld, ld> p[4];
	p[0] = {x, y};
	p[1] = {x, y+w};
	p[2] = {x+w, y};
	p[3] = {x+w, y+w};
//	cout<<coll(make_pair(0, 0), make_pair(1, 1), make_pair(1, 0), make_pair(0, 1))<<endl;
	ll ans = 0;
	for(int i = 0; i <= le; ++i) {
		side[0][i/64] |= 1ll<<(i%64);
	}
	for(int i = le; i <= le+wi; ++i) {
		side[1][i/64] |= 1ll<<(i%64);
	}
	for(int i = le+wi; i <= le*2+wi; ++i) {
		side[2][i/64] |= 1ll<<(i%64);
	}
	for(int i = le*2+wi; i < 2*le+2*wi; ++i) {
		side[3][i/64] |= 1ll<<(i%64);
	}
	side[3][0] |= 1;
	for(ll i = 0; i < le*2+wi*2; ++i) {
		t[0] = getPos(i);
		for(ll j = 0; j < le*2 + wi*2; ++j) {
			t[1] = getPos(j);
			t[2] = t[1];
			if(check(t, p)) {
				bs[i][j/64] |= 1ll<<(j%64);
			}
		}
		bs[i][i/64] &= ~(1ll<<(i%64));
	}
	for(ll i = 0; i < le*2+wi*2; ++i) {
//		cout<<getPos(i).F<<' '<<getPos(i).S<<'\n';
		t[0] = getPos(i);
	//	cout<<"lol "<<endl;
		for(ll j = 0; j < le*2 + wi*2; ++j) {
			t[1] = getPos(j);
			t[2] = t[1];
			if(i == j) continue;
			if(check(t, p) == 0) continue;
	//		cout<<i<<' '<<t[0].F<<' '<<t[0].S<<' '<<t[1].F<<' '<<t[1].S<<' '<<check(t, p)<<'\n';

			int sd = 4;
			if(t[0].F == 0 && t[1].F == 0) {
				sd = 0;
			}
			if(t[0].S == le && t[1].S == le) {
				sd = 1;
			}
			if(t[0].F == wi && t[1].F == wi) {
				sd = 2;
			}
			if(t[0].S == 0 && t[1].S == 0) {
				sd = 3;
			}

			for(int k = 0; k < 10; ++k) {
				ll q = bs[i][k] & bs[j][k];
				q &= ~side[sd][k];
				ans += __builtin_popcountll(q);
			}
			continue;

			for(ll k = j+1; k < le*2 + wi*2; ++k) {
				t[2] = getPos(k);
			if(t[0].F == t[1].F  && t[1].F == t[2].F) continue;
			if(t[0].S == t[1].S && t[1].S == t[2].S) continue;
				/*
				cout<<t[0].F<<' '<<t[0].S<<'\n';
				cout<<t[1].F<<' '<<t[1].S<<'\n';
				cout<<t[2].F<<' '<<t[2].S<<'\n';
				cout<<"LOLLERO \n";
				*/
				if(check(t, p) == 0) continue;
				//cout<<i<<" "<<j<<" "<<k<<endl;
				++ans;
			}
		}
	}
//	cout<<'\n';
	cout<<ans/6<<'\n';
	
}
int main() {
	int T;
	cin>>T;
	for(int xx = 0; xx < T; ++xx) {
		solve();
	}
}

Test 1

Verdict: ACCEPTED