U E D R , A S I H C RSS

Chocolate Chip Cookies/조현태

느낀점 및 설명

- 속도를 향상 시키는 방법은 스스로 생각해 볼것!^^

소스


~cpp
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <Windows.h>

using namespace std;

struct SMyPoint{
	double x;
	double y;
	SMyPoint(double inputX, double inputY)
	{
		x = inputX;
		y = inputY;
	}
	bool operator == (const SMyPoint& target)
	{
		return x == target.x && y == target.y;
	}
};

const double MAX_LEGTH = 5.0;
vector<SMyPoint> g_points;
vector< vector<SMyPoint> > g_hitPoints;

double GetLength(SMyPoint& one, SMyPoint another)
{
	return sqrt((one.x - another.x) * (one.x - another.x) + (one.y - another.y) * (one.y - another.y));
}

void initHitPoints()
{
	g_hitPoints.clear();
	for (register int i = 0; i < (int)g_points.size(); ++i)
	{
		vector<SMyPoint> temp;
		temp.push_back(g_points[i]);
		g_hitPoints.push_back(temp);
	}
}

int GetMaxChipNumber()
{
	initHitPoints();
	for (register int i = 0; i < (int)g_points.size(); ++i)
	{
		int nowSuchLength = (int)g_hitPoints.size();
		for (register int j = 0; j < nowSuchLength; ++j)
		{
			bool isAllHit = TRUE;
			for (register int k = 0; k < (int)g_hitPoints[j].size(); ++k)
			{
				if (MAX_LEGTH < GetLength(g_points[i], g_hitPoints[j][k]) || g_points[i] == g_hitPoints[j][k])
				{
					isAllHit = FALSE;
					break;
				}
			}
			if (isAllHit)
			{
				g_hitPoints.push_back(g_hitPoints[j]);
				g_hitPoints[(int)g_hitPoints.size() - 1].push_back(g_points[i]);
			}
		}
	}
	int maxPoint = 0;
	for (register int i = 0; i < (int)g_hitPoints.size(); ++i)
	{
		if (maxPoint < (int)g_hitPoints[i].size())
			maxPoint = (int)g_hitPoints[i].size();
	}
	return maxPoint;
}

void main()
{
	int testCaseNumber = 0;
	string oneLine;
	float pointX, pointY;
	cin >> testCaseNumber;
	getline(cin, oneLine);
	getline(cin, oneLine);
	for (register int i = 0; i < testCaseNumber; ++i)
	{
		while(1)
		{
			getline(cin, oneLine);
			if (0 == strlen(oneLine.c_str()))
			{
				cout << GetMaxChipNumber() << endl;
				break;
			}
			else
			{
				sscanf(oneLine.c_str(), "%f %f", &pointX, &pointY);
				g_points.push_back(SMyPoint(pointX, pointY));
			}
		}
	}
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:51
Processing time 0.0105 sec