CandyOnDisk.cpp

#include <iostream>
#include <ctime>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cassert>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iterator>
#include <fstream>
using namespace std;

typedef long long 		int64;
typedef vector<int> 		vi;
typedef string 			ST;
typedef stringstream 		SS;
typedef vector< vector<int> > 	vvi;
typedef pair<int,int> 		ii;
typedef vector<string> 		vs;
/*
#if __cplusplus > 199711L	// for g++0x, value of __cplusplus must be greater thana 199711L.
	#define tr(i, c)	for(auto i = begin(c); i != end(c); i++)
#else
	#define tr(i, c)	for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#endif
*/
#define endl		("\n")
#define tr(i, c)	for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define PI		M_PI
#define E 		M_E
#define	eps		1e-9

#define	Sf		scanf
#define	Pf		printf

#define forn(i, n)	for(int i = 0, lets_stop_here = (int)n; i <  lets_stop_here; i++)
#define forab(i, a, b)	for(int i = a, lets_stop_here = (int)b; i <= lets_stop_here; i++)
#define rep(i, a, b)	for(int i = a, lets_stop_here = (int)b; i >= lets_stop_here; i--)

#define	all(c)		(c).begin(), (c).end()
#define	CL(a, b)	memset(a, b, sizeof(a))
#define mp		make_pair
#define pb		push_back

#define	present(x, c)	((c).find(x) != (c).end())	//map & set//
#define	cpresent(x, c)	(find( (c).begin(), (c).end(), x) != (c).end())	//vector & list//

#define read(n)		scanf("%d", &n)
#define write(n)	printf("%d ", n)
#define writeln(n)	printf("%d\n", n)

#if (0 or defined ONLINE_JUDGE)
	#define DEBUG
#else 
	#define DEBUG(x)	cout << #x << " = " << x << "\n"
#endif

class CandyOnDisk
{
public:
	string ableToAchieve(vector <int> x, vector <int> y, vector <int> r, int sx, int sy, int tx, int ty);
};

string CandyOnDisk::ableToAchieve (vector <int> x, vector <int> y, vector <int> r, int sx, int sy, int tx, int ty) 
{
	string ret;
	
	return ret;
}

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <int> p0, vector <int> p1, vector <int> p2, int p3, int p4, int p5, int p6, bool hasAnswer, string p7) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p0[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p1.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p1[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p2.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p2[i];
	}
	cout << "}" << "," << p3 << "," << p4 << "," << p5 << "," << p6;
	cout << "]" << endl;
	CandyOnDisk *obj;
	string answer;
	obj = new CandyOnDisk();
	clock_t startTime = clock();
	answer = obj->ableToAchieve(p0, p1, p2, p3, p4, p5, p6);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << "\"" << p7 << "\"" << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << "\"" << answer << "\"" << endl;
	if (hasAnswer) {
		res = answer == p7;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	vector <int> p0;
	vector <int> p1;
	vector <int> p2;
	int p3;
	int p4;
	int p5;
	int p6;
	string p7;
	
	{
	// ----- test 0 -----
	int t0[] = {0,4};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {0,0};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {3,3};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = -1;
	p4 = -2;
	p5 = 6;
	p6 = 1;
	p7 = "YES";
	all_right = KawigiEdit_RunTest(0, p0, p1, p2, p3, p4, p5, p6, true, p7) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	int t0[] = {0,3};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {0,0};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {5,3};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = -4;
	p4 = 0;
	p5 = -2;
	p6 = 0;
	p7 = "YES";
	all_right = KawigiEdit_RunTest(1, p0, p1, p2, p3, p4, p5, p6, true, p7) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	int t0[] = {0};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {0};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {1};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = 0;
	p4 = 0;
	p5 = 571;
	p6 = 571;
	p7 = "NO";
	all_right = KawigiEdit_RunTest(2, p0, p1, p2, p3, p4, p5, p6, true, p7) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	int t0[] = {0};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {0};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {1};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = 571;
	p4 = 571;
	p5 = 571;
	p6 = 571;
	p7 = "YES";
	all_right = KawigiEdit_RunTest(3, p0, p1, p2, p3, p4, p5, p6, true, p7) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	int t0[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = 2;
	p4 = 2;
	p5 = 19;
	p6 = 19;
	p7 = "YES";
	all_right = KawigiEdit_RunTest(4, p0, p1, p2, p3, p4, p5, p6, true, p7) && all_right;
	// ------------------
	}
	
	{
	// ----- test 5 -----
	int t0[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = 2;
	p4 = 2;
	p5 = 19;
	p6 = 19;
	p7 = "NO";
	all_right = KawigiEdit_RunTest(5, p0, p1, p2, p3, p4, p5, p6, true, p7) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// Fox Ciel is playing the "DJ Box" set of levels in the "Cut the Rope" game on her smartphone.
// In the current level, she is facing the following problem:
// 
// 
// 
// The level can be seen as a two-dimensional plane that contains a single candy and some disks.
// You are given the description of the level: vector <int>s x, y, and r; and ints sx, sy, tx, and ty.
// 
// 
// 
// The vector <int>s x, y, and r describe the disks:
// For each i, there is a disk centered at (x[i], y[i]) with radius r[i].
// Some of the disks may overlap.
// The candy is initially located at (sx, sy), and the goal of the game is to move it to (tx, ty).
// 
// 
// 
// The game is played by rotating some of the disks, one after another.
// More precisely, in each step, Ciel may choose any disk that currently contains the candy, and rotate the disk by any desired angle around its center.
// The candy rotates with the chosen disk.
// Other disks are ignored during the rotation.
// (If the candy is located exactly on the border of a disk, we still consider it to be on the disk.)
// 
// 
// 
// Return "YES" if she can solve the level in finitely many steps, and "NO" otherwise.
// 
// DEFINITION
// Class:CandyOnDisk
// Method:ableToAchieve
// Parameters:vector <int>, vector <int>, vector <int>, int, int, int, int
// Returns:string
// Method signature:string ableToAchieve(vector <int> x, vector <int> y, vector <int> r, int sx, int sy, int tx, int ty)
// 
// 
// CONSTRAINTS
// -x will contain between 1 and 50 elements, inclusive.
// -x, y, and r will each contain the same number of elements.
// -Each element in x, y will be between -1,000,000,000 and 1,000,000,000, inclusive.
// -Each element in r will be between 1 and 1,000,000,000, inclusive.
// -sx, sy, tx and ty will be between -1,000,000,000 and 1,000,000,000, inclusive.
// -The answer will not change if we increase the radii of all disks by 1e-3. Neither will it change if we decrease the radii of all disks by 1e-3.
// 
// 
// EXAMPLES
// 
// 0)
// {0, 4}
// {0, 0}
// {3, 3}
// -1
// -2
// 6
// 1
// 
// Returns: "YES"
// 
// 
// 
// You have two disks. You can win the level by first rotating the yellow disk to move the candy from S to A = (2,1), and then rotating the green disk to move the candy from A to T.
// 
// 1)
// {0, 3}
// {0, 0}
// {5, 3}
// -4
// 0
// -2
// 0
// 
// Returns: "YES"
// 
// 
// 
// This time you need 3 steps: S->A->B->T.
// 
// 2)
// {0}
// {0}
// {1}
// 0
// 0
// 571
// 571
// 
// Returns: "NO"
// 
// The target point is outside of the only disk, so we clearly cannot reach it.
// 
// 3)
// {0}
// {0}
// {1}
// 571
// 571
// 571
// 571
// 
// Returns: "YES"
// 
// 
// 
// 4)
// {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
// {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
// {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}
// 2
// 2
// 19
// 19
// 
// Returns: "YES"
// 
// 
// 
// 5)
// {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
// {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
// {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
// 2
// 2
// 19
// 19
// 
// Returns: "NO"
// 
// 
// 
// END KAWIGIEDIT TESTING

//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!