76db68d634 2018-07-28        kinaba: #include <iostream>
76db68d634 2018-07-28        kinaba: #include <sstream>
76db68d634 2018-07-28        kinaba: #include <iomanip>
76db68d634 2018-07-28        kinaba: #include <vector>
76db68d634 2018-07-28        kinaba: #include <string>
76db68d634 2018-07-28        kinaba: #include <map>
76db68d634 2018-07-28        kinaba: #include <unordered_map>
76db68d634 2018-07-28        kinaba: #include <set>
76db68d634 2018-07-28        kinaba: #include <algorithm>
76db68d634 2018-07-28        kinaba: #include <numeric>
76db68d634 2018-07-28        kinaba: #include <iterator>
76db68d634 2018-07-28        kinaba: #include <functional>
76db68d634 2018-07-28        kinaba: #include <complex>
76db68d634 2018-07-28        kinaba: #include <queue>
76db68d634 2018-07-28        kinaba: #include <stack>
76db68d634 2018-07-28        kinaba: #include <cmath>
76db68d634 2018-07-28        kinaba: #include <cassert>
76db68d634 2018-07-28        kinaba: #include <tuple>
76db68d634 2018-07-28        kinaba: using namespace std;
76db68d634 2018-07-28        kinaba: typedef long long LL;
76db68d634 2018-07-28        kinaba: typedef complex<double> CMP;
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: class PolylineAreas { public:
76db68d634 2018-07-28        kinaba: 	vector<long long> findAreas(string polyline)
76db68d634 2018-07-28        kinaba: 	{
76db68d634 2018-07-28        kinaba: 		string cmd;
76db68d634 2018-07-28        kinaba: 		{
76db68d634 2018-07-28        kinaba: 			const char* p = polyline.c_str();
76db68d634 2018-07-28        kinaba: 			while (*p)
76db68d634 2018-07-28        kinaba: 				parse_one(p, cmd);
76db68d634 2018-07-28        kinaba: 		}
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 		#define enc(x,y) ((LL(x+1000000)<<32)|(y+1000000))
76db68d634 2018-07-28        kinaba: 		const int dx[] = { 1, 0, -1, 0 };
76db68d634 2018-07-28        kinaba: 		const int dy[] = { 0, 1, 0, -1 };
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 		unordered_map<LL, int> edge;
76db68d634 2018-07-28        kinaba: 		{
76db68d634 2018-07-28        kinaba: 			int x = 0, y = 0, d = 0;
76db68d634 2018-07-28        kinaba: 			for (int ch : cmd) {
76db68d634 2018-07-28        kinaba: 				switch (ch) {
76db68d634 2018-07-28        kinaba: 				case 'F': {
76db68d634 2018-07-28        kinaba: 					LL p = enc(x, y);
76db68d634 2018-07-28        kinaba: 					x += dx[d];
76db68d634 2018-07-28        kinaba: 					y += dy[d];
76db68d634 2018-07-28        kinaba: 					LL c = enc(x, y);
76db68d634 2018-07-28        kinaba: 					edge[p] |= 1 << d;
76db68d634 2018-07-28        kinaba: 					edge[c] |= 1 << ((d + 2) % 4);
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 					break;
76db68d634 2018-07-28        kinaba: 				}
76db68d634 2018-07-28        kinaba: 				case 'L': d = (d + 1) % 4; break;
76db68d634 2018-07-28        kinaba: 				case 'R': d = (d + 3) % 4; break;
76db68d634 2018-07-28        kinaba: 				}
76db68d634 2018-07-28        kinaba: 			}
76db68d634 2018-07-28        kinaba: 		}
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 		vector<LL> ans;
76db68d634 2018-07-28        kinaba: 		{
76db68d634 2018-07-28        kinaba: 			for (auto pd : edge) {
76db68d634 2018-07-28        kinaba: 				const int s_x = int(pd.first >> 32) - 1000000;
76db68d634 2018-07-28        kinaba: 				const int s_y = int(pd.first & 0xffffffff) - 1000000;
76db68d634 2018-07-28        kinaba: 				int& ds = pd.second;
76db68d634 2018-07-28        kinaba: 				for (int d = 0; d < 4; ++d) if (ds&(1 << d)) {
76db68d634 2018-07-28        kinaba: 					// go clockwise from (x,y) -> d
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 					LL area = 0;
76db68d634 2018-07-28        kinaba: 					int x = s_x, y = s_y;
76db68d634 2018-07-28        kinaba: 					do {
76db68d634 2018-07-28        kinaba: 						//cerr << "(" << x << "," << y << "): " << d << endl;
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 						// move
76db68d634 2018-07-28        kinaba: 						int px = x, py = y;
76db68d634 2018-07-28        kinaba: 						x += dx[d];
76db68d634 2018-07-28        kinaba: 						y += dy[d];
76db68d634 2018-07-28        kinaba: 						edge[enc(px, py)] &= ~(1 << d);
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 						// turn
76db68d634 2018-07-28        kinaba: 						int& dd = edge[enc(x, y)];
76db68d634 2018-07-28        kinaba: 						if (dd & (1 << ((d + 3) % 4)))
76db68d634 2018-07-28        kinaba: 							d = (d + 3) % 4;
76db68d634 2018-07-28        kinaba: 						else if (dd & (1 << d))
76db68d634 2018-07-28        kinaba: 							;
76db68d634 2018-07-28        kinaba: 						else if (dd & (1 << ((d + 1) % 4)))
76db68d634 2018-07-28        kinaba: 							d = (d + 1) % 4;
76db68d634 2018-07-28        kinaba: 						else if (dd & (1 << ((d + 2)%4)))
76db68d634 2018-07-28        kinaba: 							d = (d + 2) % 4;
76db68d634 2018-07-28        kinaba: 						else
76db68d634 2018-07-28        kinaba: 							break;
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 						// calc area
76db68d634 2018-07-28        kinaba: 						area += LL(x - s_x)*(py - s_y) - LL(px-s_x)*(y-s_y);
76db68d634 2018-07-28        kinaba: 						//cerr << LL(x - s_x)*(py - s_y) - LL(px - s_x)*(y - s_y) << endl;
76db68d634 2018-07-28        kinaba: 					} while (x != s_x || y != s_y);
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 					if(x==s_x && y==s_y && area > 0)
76db68d634 2018-07-28        kinaba: 						ans.push_back(area/2);
76db68d634 2018-07-28        kinaba: 				}
76db68d634 2018-07-28        kinaba: 			}
76db68d634 2018-07-28        kinaba: 		}
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 		sort(ans.begin(), ans.end());
76db68d634 2018-07-28        kinaba: 		if (ans.size() > 200) {
76db68d634 2018-07-28        kinaba: 			vector<LL> a2(ans.begin(), ans.begin() + 100);
76db68d634 2018-07-28        kinaba: 			a2.insert(a2.end(), ans.end() - 100, ans.end());
76db68d634 2018-07-28        kinaba: 			return a2;
76db68d634 2018-07-28        kinaba: 		}
76db68d634 2018-07-28        kinaba: 		return ans;
76db68d634 2018-07-28        kinaba: 	}
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 	void parse_one(const char*& p, string& buf) {
76db68d634 2018-07-28        kinaba: 		if ('0' <= *p && *p <= '9') {
76db68d634 2018-07-28        kinaba: 			int rep = (*p++ - '0');
76db68d634 2018-07-28        kinaba: 			while('0' <= *p && *p <= '9')
76db68d634 2018-07-28        kinaba: 				rep = rep*10 + (*p++ - '0');
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 			string sub;
76db68d634 2018-07-28        kinaba: 			parse_one(p, sub);
76db68d634 2018-07-28        kinaba: 			while (rep-- > 0)
76db68d634 2018-07-28        kinaba: 				buf += sub;
76db68d634 2018-07-28        kinaba: 		}
76db68d634 2018-07-28        kinaba: 		else if (*p == '[') {
76db68d634 2018-07-28        kinaba: 			for (++p; *p != ']'; )
76db68d634 2018-07-28        kinaba: 				parse_one(p, buf);
76db68d634 2018-07-28        kinaba: 			++p;
76db68d634 2018-07-28        kinaba: 		}
76db68d634 2018-07-28        kinaba: 		else {
76db68d634 2018-07-28        kinaba: 			buf += *p++;
76db68d634 2018-07-28        kinaba: 		}
76db68d634 2018-07-28        kinaba: 	}
76db68d634 2018-07-28        kinaba: };
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: // BEGIN CUT HERE
76db68d634 2018-07-28        kinaba: #include <ctime>
76db68d634 2018-07-28        kinaba: double start_time; string timer()
76db68d634 2018-07-28        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
76db68d634 2018-07-28        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
76db68d634 2018-07-28        kinaba:  { os << "{ ";
76db68d634 2018-07-28        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
76db68d634 2018-07-28        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
76db68d634 2018-07-28        kinaba: void verify_case(const vector<long long>& Expected, const vector<long long>& Received) {
76db68d634 2018-07-28        kinaba:  bool ok = (Expected == Received);
76db68d634 2018-07-28        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
76db68d634 2018-07-28        kinaba:  cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
76db68d634 2018-07-28        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
76db68d634 2018-07-28        kinaba: #define END	 verify_case(_, PolylineAreas().findAreas(polyline));}
76db68d634 2018-07-28        kinaba: int main(){
76db68d634 2018-07-28        kinaba: CASE(0)
76db68d634 2018-07-28        kinaba: 	string polyline = "FRFLF";
76db68d634 2018-07-28        kinaba: 	vector<long long> _;
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: CASE(1)
76db68d634 2018-07-28        kinaba: 	string polyline = "4[100FR]";
76db68d634 2018-07-28        kinaba: 	long long __[] = {10000 };
76db68d634 2018-07-28        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: CASE(2)
76db68d634 2018-07-28        kinaba: 	string polyline = "2[2[100FR]]";
76db68d634 2018-07-28        kinaba: 	long long __[] = {10000 };
76db68d634 2018-07-28        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: CASE(3)
76db68d634 2018-07-28        kinaba: 	string polyline = "47[100FR]";
76db68d634 2018-07-28        kinaba: 	long long __[] = {10000 };
76db68d634 2018-07-28        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: CASE(4)
76db68d634 2018-07-28        kinaba: 	string polyline = "1000000[]";
76db68d634 2018-07-28        kinaba: 	vector<long long> _;
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: CASE(5)
76db68d634 2018-07-28        kinaba: 	string polyline = "4[6FR]FR6FL2FL6FR3FRFR6FL2FL6F";
76db68d634 2018-07-28        kinaba: 	long long __[] = {1, 2, 2, 3, 3, 4, 6, 6, 9 };
76db68d634 2018-07-28        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: CASE(6)
76db68d634 2018-07-28        kinaba: 	string polyline = "4[6FR]FR6FL2FL6FR3FRFR6FL2FL4F";
76db68d634 2018-07-28        kinaba: 	long long __[] = {1, 2, 2, 3, 3, 4, 6, 15 };
76db68d634 2018-07-28        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: CASE(7)
76db68d634 2018-07-28        kinaba: 	string polyline = "3FRFRFLFLFRFR3FRFRFLFLFRF";
76db68d634 2018-07-28        kinaba: 	long long __[] = {7 };
76db68d634 2018-07-28        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: CASE(8)
76db68d634 2018-07-28        kinaba: 	string polyline = "250000F";
76db68d634 2018-07-28        kinaba:     long long __[] = {-1};
76db68d634 2018-07-28        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: /*
76db68d634 2018-07-28        kinaba: CASE(9)
76db68d634 2018-07-28        kinaba: 	string polyline = ;
76db68d634 2018-07-28        kinaba: 	long long __[] = ;
76db68d634 2018-07-28        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: */
76db68d634 2018-07-28        kinaba: }
76db68d634 2018-07-28        kinaba: // END CUT HERE