Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
2.7 kB
129
Indexable
Never
#define fst first
#define snd second
#define MP make_pair
#define FOR(i, n) for (int i = 0; i < n; i++)
#define FORL(i, m, n) for (int i = m; i < n; i++)
#define FORV(i, v) for (int i = 0; i < v.size(); i++)

typedef long long LL;
typedef pair<LL, LL> PII;

char ToDir(char s) {
	if (s == '0') return 'e';
	if (s == '1') return 's';
	if (s == '2') return 'w';
	return 'n';
}

PII NextPt(PII p, char d, LL n) {
	if (d == 'e') return MP(p.fst, p.snd + n);
	if (d == 'w') return MP(p.fst, p.snd - n);
	if (d == 'n') return MP(p.fst - n, p.snd);
	return MP(p.fst + n, p.snd);
}

LL FromHexChar(char c) {
	if (c >= '0' && c <= '9') return FromChar(c);
	return int(c - 'a') + 10LL;
}

LL FromHex(const string& s) {
	LL ret = 0, m = 1;
	for (int i = int(s.size()) - 1; i >= 0; i--) {
		ret += FromHexChar(s[i]) * m;
		m *= 16;
	}
	return ret;
}

int main() {
	vector<string> lines = ReadInput();	 // ctrl-Z to terminate
	vector<LL> ns;
	string ds;
	for (string line : lines) {
		StrTok st(line);
		st.Next();
		st.Next();
		string s = st.Next();
		ns.push_back(FromHex(s.substr(2, 5)));
		ds.push_back(ToDir(s[int(s.size()) - 2]));
	}
	map<LL, vector<pair<PII, bool>>> info;  // Map each row to a series of segments within that row
	PII cur = MP(0, 0);
	FORV(k, ds) {
		if (ds[k] == 'e' || ds[k] == 'w') {  // e/w segment
			int pk = (k == 0 ? int(ds.size()) - 1 : k - 1);
			int nk = (k == int(ds.size()) - 1 ? 0 : k + 1);
			bool inflect = (ds[pk] == ds[nk]);  // Is this e/w segment an "inflection" shape?
			if (ds[k] == 'e') {
				info[cur.fst].push_back(MP(MP(cur.snd, cur.snd + ns[k]), inflect));
			}
			else {
				info[cur.fst].push_back(MP(MP(cur.snd - ns[k], cur.snd), inflect));
			}
		}
		else {  // vertical wall (i.e. length-1 segment)
			FORL(i, 1, ns[k]) {
				info[(ds[k] == 'n') ? cur.fst - i : cur.fst + i].push_back(MP(MP(cur.snd, cur.snd), false));
			}
		}
		cur = NextPt(cur, ds[k], ns[k]);
	}
	LL ans = 0;
	for (auto x : info) {
		sort(x.snd.begin(), x.snd.end());  // Consider segments in the row from left to right
		bool inside = false;  // Are we inside the polygon?
		LL prev = -1;
		FORV(i, x.snd) {
			if (x.snd[i].fst.fst == x.snd[i].fst.snd) {  // vertical wall
				++ans;
				if (inside) ans += x.snd[i].fst.fst - prev - 1;
				inside = !inside;
				prev = x.snd[i].fst.fst;
			}
			else {  // e/w segment
				ans += x.snd[i].fst.snd - x.snd[i].fst.fst + 1;
				if (inside)	ans += x.snd[i].fst.fst - prev - 1;
				if (x.snd[i].snd) inside = !inside;  // Only flip inside-ness on "inflection"-shaped segments
				prev = x.snd[i].fst.snd;
			}
		}
	}
	cout << ans << endl;
	return 0;
}
Leave a Comment