2065891_ac_171ms_28k.cpp

北大大牛代码 1240道题的原代码 超级权威

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

struct node
{
	int i;
	int j;
	int u;
}pot[10];

void add(char Tmp[],int n)
{
	int i, l1, l2, tmp, w, max;
	char ch, ch1, ch2, t1[2];

	itoa(n,t1,10);
	l1 = strlen(Tmp);
	l2 = strlen(t1);
	if(l2==2)
	{
		ch = t1[0];
		t1[0] = t1[1];
		t1[1] = ch;
	}
	w = 0;
	max = l1>l2?l1:l2;
	for(i = 0; i < max; i++)
	{
		if(i < l2)
			ch1 = t1[i];
		else
			ch1 = '0';
		if(i < l1)
			ch2 = Tmp[i];
		else
			ch2 = '0';
		tmp = (ch1-'0')+(ch2-'0')+w;
		Tmp[i] = '0'+(tmp%10);
		w = tmp/10;
	}
	if(w)
		Tmp[max] = '0'+w;
	Tmp[max+(w!=0)] = '\0';
}

void minus(char temp[],char Tmp[])
{
	int i, l, lT, w, tmp;
	char ch;

	l= strlen(temp);
	lT = strlen(Tmp);
	for(i = 0; i < l/2; i++)
	{
		ch = temp[i];
		temp[i] = temp[l-i-1];
		temp[l-i-1] = ch;
	}
	if(strcmp(temp,Tmp)==0)
	{
		strcpy(temp,"0");
		return ;
	}
	w = 0;
	for(i = 0; i < l; i++)
	{
		if(i < lT)
			ch = Tmp[i];
		else
			ch = '0';
		tmp = (temp[i]-'0')-(ch-'0')-w;
		if(tmp<0)
		{
			w = 1;
			tmp += 10;
		}
		else
			w = 0;
		temp[i] = '0'+tmp;
	}
	for(i = l-1; i >= 0; i--)
		if(temp[i]!='0')
		{
			temp[i+1] = '\0';
			break;
		}
	l = strlen(temp);
	for(i = 0; i < l/2; i++)
	{
		ch = temp[i];
		temp[i] = temp[l-i-1];
		temp[l-i-1] = ch;
	}
}

void muti(char Tmp[],char t1[])
{
	int tmp, w, p;
	char ans[400];
	int l1, l2, i, j;

	l1 = strlen(Tmp);
	l2 = strlen(t1);
	p = 1;
	for(i = 0; i < 400; i++)
		ans[i] = '0';
	for(i = 0; i < l2; i++)
	{
		w = 0;
		for(j = 0; j < l1; j++)
		{
			tmp = (Tmp[j]-'0')*(t1[i]-'0')+w;
			tmp += ans[j+i]-'0';
			ans[j+i] = tmp%10+'0';
			w = tmp/10;
		}
		if(w)
			ans[j+i] = '0'+w;
	}
	if(w)
		p = 0;
	ans[j+i-p] = '\0';
	strcpy(Tmp,ans);
}

void cal(int a,int p,char ans[],char Tmp[])
{
	int i, l = 0;
	char ch, t1[4];

	itoa(a*20,t1,10);
	for(i = p; i >= 0; i--)
		Tmp[p-i] = ans[i];
	Tmp[p+1] = '\0';
	if(strlen(t1)==3)
		l = 1;
	ch = t1[0];
	t1[0] = t1[1+l];
	t1[1+l] = ch;
	if(p!=-1)
		muti(Tmp,t1);
	add(Tmp,a*a);
}

int compare(char t1[], char t2[])
{
	int i, l;
	char ch, tmp[400];

	strcpy(tmp,t1);
	l = strlen(tmp);
	for(i = 0; i < l/2; i++)
	{
		ch = tmp[i];
		tmp[i] = tmp[l-i-1];
		tmp[l-i-1] = ch;
	}
	if(strlen(tmp)<strlen(t2)||(strlen(tmp)==strlen(t2)&&strcmp(t2,tmp)>=0))
		return 1;
	return 0;
}

int check(char str[])
{
	int i;

	for(i = 0; str[i]!='\0'; i++)
		if(str[i]!='0')
			return 0;
	return 1;
}

void sqrt(char tmp[],char ans[])
{
	int i, j, l, t, p, mark;
	char ch, num[400], temp[400], t1[5], Tmp[400];

	p = -1;
	l = strlen(tmp);
	if(l%2==0)
		strcpy(num,tmp);
	else
	{
		strcpy(num,"0");
		strcat(num,tmp);
		l++;
	}
	strcpy(temp,"0");
	for(i = 0; i < l-1; i+=2)
	{
		mark = 0;
		t = (num[i]-'0')*10+(num[i+1]-'0');
		itoa(t,t1,10);
		if(t<10)
		{
			ch = t1[0];
			t1[0] = '0';
			t1[1] = ch;
			t1[2] = '\0';
		}
		if(check(temp))
			strcpy(temp,t1);
		else
			strcat(temp,t1);
		for(j = 0; temp[j] != '\0'; j++)
			if(temp[j]!='0')
			{
				strcpy(temp,&temp[j]);
				break;
			}
		for(j = 9; j > 0; j--)
		{
			cal(j,p,ans,Tmp);
			if(compare(Tmp,temp))
			{
				mark = 1;
				break;
			}
		}
		if(mark)
		{
			minus(temp,Tmp);
			ans[++p] = '0'+j;
		}
		else
			ans[++p] = '0';
	}
	ans[p+1] = '\0';
}

void reserve(char tmp[])
{
	int i, l;
	char ch;

	l = strlen(tmp);
	for(i = 0; i < l/2; i++)
	{
		ch = tmp[i];
		tmp[i] = tmp[l-i-1];
		tmp[l-i-1] = ch;
	}
}

void divide(char tmp[], int n)
{
	int l, i, t, s, mark;
	char q[400];

	l = strlen(tmp);
	i = t = 0;
	mark = 1;
	while(1&&mark)
	{	
		while(t<n&&i<l)
		{
	     	t *= 10;
	     	t += tmp[i]-'0';
			q[i] = '0';
			i++;
		}
		s = t / n;
		if(!s)
			mark = 0;
		if(mark)
			q[i-1] = s+'0';
		t -= s*n;
	}
	q[i] = '\0';
	for(i = 0; q[i] != '\0'; i++)
		if(q[i]!='0')
		{
			strcpy(q,&q[i]);
    		break;
		}
	strcpy(tmp,q);
}

int work(char tmp[],char u1[])
{
	int pot;
	char ua[400], ua2[400], ans[400];

	strcpy(u1,tmp);
	reserve(tmp);
	muti(tmp,"8");
	add(tmp,1);
	reserve(tmp);
	sqrt(tmp,ans);
	minus(ans,"1");
	divide(ans,2);
	strcpy(ua,ans);
	reserve(ans);
	strcpy(ua2,ans);		
	add(ans,1);
	muti(ua2,ans);
	reserve(ua2);
	divide(ua2,2);
	reserve(ua2);
	minus(u1,ua2);
	reserve(u1);
	minus(ua,u1);
	reserve(u1);
	pot = atoi(ua);
	return pot;
}

void input()
{
	int i, n, A;
	double s;
	char tmp[400], u1[400], tmpu[400];

	while(scanf("%s",tmp)==1&&strcmp(tmp,"*")!=0)
	{		
		n = work(tmp,u1);
		for(i = 0; i < n-1; i++)
		{
			pot[i].u = work(u1,tmpu);
			strcpy(u1,tmpu);
		}
		pot[i].u = atoi(u1);
		for(i = 0; i < n; i++)
		{
			A = (int)((sqrt(1+8*pot[i].u)-1)/2.0);
			pot[i].j = pot[i].u-A*(A+1)/2;
			pot[i].i = A - pot[i].j;
		}
		s = 0;
		for(i = 0; i < n; i++)
			s += pot[i].i*pot[(i+1)%n].j-pot[i].j*pot[(i+1)%n].i;
		s /= 2.0;
		if(s<0)
			s*=-1;
		printf("%.1lf\n",s);
	}
}

int main()
{
	input();
	return 1;
}