sector.c

問題はこちら
http://nabetani.sakura.ne.jp/hena/ord19nebasec/

他の解答例はこちら
http://qiita.com/Nabetani/items/9810b301648099028bf0

★作戦
極座標を考えて、角度の範囲の重なりを調べて、隣接しているか確認しています。

★境界部分の処理（例　セクタ100と107など）
例えば、セクタ100が不良であれば、セクタ108（番兵）を不良セクタに登録しています。

# include <stdio.h>
# include <stdlib.h>
# include <string.h>

void str2ary(const char *str, int *bad_r, int *bad_th)
{
	int th_cnt[] = {0, 8, 16, 24, 32};
	char *s1 = strdup(str);
	char *code = strtok(s1, ",");
	for(int i = 0; code != NULL; i++)
	{
		int num = atoi(code);
		bad_r[i] = num/100;
		bad_th[i] = num%100;
		if(bad_th[i] == 0)
		{
			i++;
			bad_r[i] = bad_r[i-1];
			bad_th[i] = th_cnt[bad_r[i-1]];
		}
		else if (bad_th[i] == th_cnt[bad_r[i]]-1)
		{
			i++;
			bad_r[i] = bad_r[i-1];
			bad_th[i] = -1;
		}
		code = strtok(NULL, ",");
	}
	free(s1);
}

int check_th(int r1, int th1, int r2, int th2)
{
	int th_r[] = {0, 360000/8, 360000/16, 360000/24, 360000/32};
	int check = (((th_r[r1]*th1) - th_r[r1]/2) <= ((th_r[r2]*th2) - th_r[r2]/2)
			&&   ((th_r[r1]*th1) + th_r[r1]/2) >= ((th_r[r2]*th2) - th_r[r2]/2))
			||	(((th_r[r1]*th1) - th_r[r1]/2) <= ((th_r[r2]*th2) + th_r[r2]/2)
			&&   ((th_r[r1]*th1) + th_r[r1]/2) >= ((th_r[r2]*th2) + th_r[r2]/2));
	return check;
}

void solve(const char* str, char *res)
{
	int bad_r[30] = {0}, bad_th[30] = {0};
	str2ary(str, bad_r, bad_th);

	int th_cnt[] = {0, 8, 16, 24, 32};
	for(int r = 1; r <= 4; r++)
	{
		for(int th = 0; th < th_cnt[r]; th++)
		{
			//printf("r,th\t%d,%d\n", r, th);
			int cnt = 0;
			for(int j = 0; bad_r[j] != 0; j++)
			{
				int br = bad_r[j], bth = bad_th[j];
				if(br == r+1)
				{
					//printf("%d,%d\n", r, th);
					if(check_th(r, th, br, bth))
					{
						cnt++;
						//printf("br1,bth1\t%d,%d\n", br, bth);
					}
				}
				else if(br == r-1)
				{
					if(check_th(br, bth, r, th))
					{
						cnt++;
						//printf("br2,bth2\t%d,%d\n", br, bth);
					}
				}
				else if ( br == r )
				{
					if(bth == th+1 || bth == th-1)
					{
						//printf("%d,%d\n", br, bth);
						cnt++;
					}
				}
				if(cnt >= 2)
				{
					int b_check = 0;
					for(int k = 0; bad_r[k] != 0; k++)
					{
						b_check |= (r == bad_r[k] && th == bad_th[k]);
					}
					if(b_check != 1)
					{
						char tmp[10] = {0};
						sprintf(tmp, "%d,", 100*r+th);
						strcat(res, tmp);
					}
					break;
				}
			}
		}
	}
	//printf("%s\n", res);
}

void test(const char *str, const char *ans)
{
	static int n = 0;
	char res[30] = {0};
	solve(str, res);
	if(strlen(res)==0)
	{
		strcat(res,"none");
	}
	printf("%d\t%s\t%s\n", n++, res, (strncmp(res, ans, strlen(ans)) == 0) ? "OK": "***ng***");
}

int main ()
{
	/*0*/ test( "400,401,302", "300,301,402" );
	/*1*/ test( "105,100,306,414", "none" );
	/*2*/ test( "100", "none" );
	/*3*/ test( "211", "none" );
	/*4*/ test( "317", "none" );
	/*5*/ test( "414", "none" );
	/*6*/ test( "100,106", "107" );
	/*7*/ test( "205,203", "102,204" );
	/*8*/ test( "303,305", "304" );
	/*9*/ test( "407,409", "306,408" );
	/*10*/ test( "104,103", "207" );
	/*11*/ test( "204,203", "102,305" );
	/*12*/ test( "313,314", "209,418" );
	/*13*/ test( "419,418", "314" );
	/*14*/ test( "100,102,101", "201,203" );
	/*15*/ test( "103,206,309", "205,207,308,310" );
	/*16*/ test( "414,310,309", "206,311,413" );
	/*17*/ test( "104,102,206,307,102,202", "101,103,203,204,205,207,308" );
	/*18*/ test( "104,206,308,409,407", "103,205,207,306,307,309,408,410" );
	/*19*/ test( "313,406,213,301,409,422,412,102,428", "none" );
	/*20*/ test( "101,300,210,308,423,321,403,408,415", "none" );
	/*21*/ test( "304,316,307,207,427,402,107,431,412,418,424", "none" );
	/*22*/ test( "205,408,210,215,425,302,311,400,428,412", "none" );
	/*23*/ test( "200,311,306,412,403,318,427,105,420", "none" );
	/*24*/ test( "105,305,407,408,309,208,427", "104,209,306,406" );
	/*25*/ test( "311,304,322,404,429,305,316", "203,303,321,405,406,430" );
	/*26*/ test( "210,401,316,425,101", "211,315" );
	/*27*/ test( "414,403,404,416,428,421", "303,415" );
	/*28*/ test( "207,300,103,211,428", "104,206" );
	/*29*/ test( "322,314,310", "none" );
	/*30*/ test( "427,200,215", "100,323" );
	/*31*/ test( "311,402,424,307,318,430,323,305,201", "200,204,301,302,306,322,423,425,431" );
	/*32*/ test( "425,430,408", "none" );
	/*33*/ test( "202,320,209,426", "319,427" );
	/*34*/ test( "430,209,302,310,304,431,320", "202,303,323" );
	/*35*/ test( "208,206,406,424,213,312", "207,311,313" );
	/*36*/ test( "420,302,313,413,317,402", "301,403" );
	/*37*/ test( "319,306,309,418,204,411", "305,307,308,412" );
	/*38*/ test( "400,308,105,430,203,428,209", "104,210,429,431" );
	/*39*/ test( "200,305,214", "215" );
	/*40*/ test( "214,408,410,407,317,422", "306,316,409,423" );
	return 0;
}