OJ Board

Code: Select all

Input:
1000000
999999
99999
9999
999
9
1
0
2
3

Output:
1024000
1222221
299997
29997
2997
27
Not Exist!
Not Exist!
4
9

Code: Select all

Code removed after acceptance.

Code: Select all

Code removed after acceptance.

Code: Select all

Code removed after acceptance.

Code: Select all

Code removed after acceptance.

Code: Select all

Code removed after acceptance.

Code: Select all

int abs(int a)
{
	return a>=0?a:-1*a;
}

Code: Select all

double dist(Axis a,Axis b)
{
	double x = pow(a.x - b.x , (double) 2);
	double y = pow(a.y - b.y , (double) 2);

	return pow(x+y,(double)0.5);

}

Code: Select all

int ccw(int x1,int y1, int x2, int y2,int x3 , int y3)
{
return  (x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1) ;
}

Code: Select all

double Angle(int x1,int y1, int x2, int y2)
{
	if(x1 == x2)
	{
		if(y2>=y1)
		{
			return 90;
		}
		else
		{
			return 270;
		}
	}

	int dy = y2 - y1;
	int dx = x2 - x1;
	double ang ;
	ang  = (double)atan((double)dy /(double) dx ) / PI * (Circle / 2 );

	if( x2 -x1 < 0 )
	{
		ang += 180;
	}
	if( y2 - y1 <0)
	{
		ang += 360;
	}
	

	return ang;

}

Code: Select all

void sorting(int N)
{
	Axis temp;
	
	
		for(int j = 1 ; j<N ; j++)
		{
			for(int k = j + 1; k<N ; k++)
			
				if(Angle(axis[0].x,axis[0].y,axis[j].x,axis[j].y ) > Angle(axis[0].x,axis[0].y,axis[k].x,axis[k].y ) )
				{
					temp.x = axis[j].x;
					axis[j].x = axis[k].x;
					axis[k].x = temp.x;

					temp.y = axis[j].y;
					axis[j].y = axis[k].y;
					axis[k].y = temp.y;


				}

				else if(Angle(axis[0].x,axis[0].y,axis[j].x,axis[j].y ) == Angle(axis[0].x,axis[0].y,axis[k].x,axis[k].y )  )
				{
					

					if(dist(axis[0],axis[j] ) < dist(axis[0],axis[k]) )
					{
						temp = axis[j];
						axis[j] = axis[k];
						axis[k] = temp;

					}


				}
			}

		
}

Code: Select all

int main()
{
	
	int cnt;
	int ci;

	cin>>cnt;
	bool blank = false;

	while(cnt)
	{
		
		
		Axis print[120];
		int convex_hull[120];
		int ribbon;
		int nailNumber;
		int xt;
		int yt;
		int si = 0;
		int nt;
		int i = 0 , j = 0;
		

		cin>>ribbon>>nailNumber;
		
		nt = nailNumber;
		while(nt)
		{
			cin>>xt>>yt;
			axis[si].x = xt;
			axis[si].y = yt;
			si++;

			
			nt--;
		}

		if(blank == false)
		{
			blank  = true;
		}
		else
		{
			cout<<endl;
		}
		if(nailNumber == 1){float rib = ribbon;printf("%.5f\n",rib + 0);cnt--;continue;}


		//	cout<<"x"<<endl;
		axis[si].x = axis[1].x;
		axis[si].y = axis[1].y;


		int min = 0;
		ci = 1;
		
		for(i = 1; i<nailNumber ; i++)
		{
			if(axis[i].y < axis[min].y)
				min = i;
		}

		//cout<<min<<endl;

		int lowest = 0;

		for(j = 0 ; j<nailNumber; j++)
		{
			if(axis[j].y == axis[min].y)
				if(axis[j].x < axis[min].x)
				{
					lowest = j;
				

				}
		}



		int temp;

		temp = axis[lowest].x;
		axis[lowest].x = axis[0].x;
		axis[0].x = temp;
		
		temp  = axis[lowest].y;
		axis[lowest].y = axis[0].y;
		axis[0].y = temp;

			

			
		sorting(nailNumber);

	
		int stk[101];
		memset(stk,0,sizeof(stk));
		stk[0] = 0;
		stk[1] = 1;
		int ccnt = 2;

		int k = 0;
		
		stk[0] = 0;
		stk[1] = 1;

		for(int d = 1; d<nailNumber ; d++)
		{
			cout<<Angle(axis[0].x,axis[0].y,axis[d].x,axis[d].y)<<endl;
		}
	
		
		for(i = 2 ; i < nailNumber ; i++)
		{	
			while(ccnt >= 2 && ccw(axis[stk[ccnt-2]].x,axis[stk[ccnt-2]].y,axis[stk[ccnt-1]].x,axis[stk[ccnt-1]].y,axis[i].x,axis[i].y) <= 0)
			{
				
				ccnt--;
			}

			stk[ccnt] = i;
			ccnt++;
	
		}
		

	

		long  double length = 0.0;

		for(int q = 0 ; q<=ccnt ; q++)
		{
			
			length += dist( axis[ stk[q] ] , axis[stk[q+1]] );
			
			
		}

		if(ribbon >length)
		{
			float rib = ribbon;
			printf("%.5f\n",rib);
		}
		else
		{
			printf("%.5f\n",length);
		}


		cnt--;
	}
return 0;


}

Code: Select all

removed afted AC