Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

why always WA?

Posted by 71105206lwj at 2007-10-01 14:30:51 on Problem 3334
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

struct Dimen_2
{
	int x;
	int y;
};

struct Digra_2
{
	Dimen_2 _point[1500];

	int count;
	int _min;
	int end_min;
};

void Init(Digra_2 &P)
{
	cin >> P.count;

	if(P.count == 0)
	{
		exit(1);
	}
	int s;
	P._min = P.end_min = 0;
	for(s = 0; s < P.count; s ++)
	{
		cin >> P._point[s].x >> P._point[s].y;
		if(P._point[s].y < P._point[P._min].y)
		{
			P._min = s;
		}
	}

	if(P._point[s-1].y < P._point[P.end_min].y)
	{
		P.end_min = s-1;
	}
}

double Pour ( Digra_2 &P, double Volume)
{
	double temp;

	int s = P._min - 1, t = P._min + 1;

	double x0, y0, x1, y1, x2, y2 , x3, y3;
	x0 = x1 = P._point[P._min].x;
	y0 = y1 = P._point[P._min].y;
	double high = 0;

	while( fabs(Volume) >1e-7 && s >= 0 && t < P.count)
	{
		if(P._point[s].y > P._point[t].y)
		{
			y2 = y3 = P._point[t].y;
			x3 = P._point[t].x;
			x2 = - y2 * P._point[s].x + x0  * y2 + y0 * P._point[s].x  - x0 * P._point[s].y;

			x2 = x2 / 1.0 / (y0 - P._point[s].y);
			t ++;
		}
		else 
		{
			y2 = y3 = P._point[s].y;
			x2 = P._point[s].x;
			x3 = - x1 * P._point[t].y + x1  * y3 - y3 * P._point[t].x  + y1 * P._point[t].x;

			x3 = x3 / 1.0 / (y1 - P._point[t].y);
			s --;
		}

		temp = (x1 - x0 + x3 - x2) * (y3  - y1) / 2.0;
		if(fabs(temp - Volume)>1e-7)
		{
			double l = (x3 - x2) * (x3 - x2) - (x1 - x0) * (x1 - x0);
			double m = (x1 - x0);
			double n = 4 * Volume * temp;
			high += (- m + sqrt (m * m + l * n)) / l;
			Volume = 0;
		}
		else
		{
			Volume -= temp;
			high += y3 - y0;
		}

		x0 = x2, y0 = y2;
		x1 = x3, y1 = y3;
	}

	return high + P._point[P._min].y;
}

double Pour (Digra_2 &P, Digra_2 &Q, double Volume)
{
	double temp;
	int s1 = P._min - 1, t1 = P._min + 1;
	int s2 = P._min - 1, t2 = P._min + 1;
	double high = 0;

	double x0, y0, x1, y1, x2, y2, x3, y3, x4, y4, x5, y5, x6, y6, x7, y7;
	x0 = x1 = P._point[P._min].x;
	y0 = y1 = P._point[P._min].y;
	x4 = x5 = x6 = x7 = Q._point[Q._min].x;
	y4 = y5 = y6 = y7 = Q._point[Q._min].y;

	while(fabs(Volume) >1e-7 && y0 < Q._point[Q._min].y && s1 >= 0 && t1 < P.count)
	{
		if(P._point[s1].y > P._point[t1].y)
		{
			y2 = y3 = P._point[t1].y;
			x3 = P._point[t1].x;
			x2 = - y2 * P._point[s1].x + x0  * y2 + y0 * P._point[s1].x  - x0 * P._point[s1].y;

			x2 = x2 / 1.0 / (y0 - P._point[s1].y);
			t1 ++;
		}
		else 
		{
			y2 = y3 = P._point[s1].y;
			x2 = P._point[s1].x;
			x3 = - x1 * P._point[t1].y + x1  * y3 - y3 * P._point[t1].x  + y1 * P._point[t1].x;

			x3 = x3 / 1.0 / (y1 - P._point[t1].y);
			s1 --;
		}

		if( y2 > Q._point[Q._min].y)
		{
			y2 = y3 = Q._point[Q._min].y;
		}
		temp = (x1 - x0 + x3 - x2) * (y3  - y1) / 2.0;
		if(fabs(temp - Volume)>1e-7)
		{
			double l = (x3 - x2) * (x3 - x2) - (x1 - x0) * (x1 - x0);
			double m = (x1 - x0);
			double n = 4 * Volume * temp;
			high += (- m + sqrt (m * m + l * n)) / l;
			Volume = 0;
		}
		else
		{
			Volume -= temp;
			high += y3 - y0;
		}

		x0 = x2, y0 = y2;
		x1 = x3, y1 = y3;

	}

	while( fabs(Volume) >1e-7 && s1 >= 0 && t1 < P.count && s2 >= 0 && t2 < Q.count)
	{
		if( P._point[s1].y <= P._point[t1].y && P._point[s1].y <= Q._point[t2].y && P._point[s1].y <= Q._point[s2].y )
		{
			y2 = y3 = y6 = y7 = P._point[s1].y;
			x2 = P._point[s1].x;
			x3 = - x1 * P._point[t1].y + x1  * y3 - y3 * P._point[t1].x  + y1 * P._point[t1].x;

			x3 = x3 / 1.0 / (y1 - P._point[t1].y);
			x6 = - x4 * Q._point[s2].y + x4  * y6 - y6 * Q._point[s2].x  + y4 * Q._point[s2].x;

			x6 = x6 / 1.0 / (y4 - P._point[s2].y);
			x7 = - x5 * Q._point[t2].y + x5  * y7 - y7 * Q._point[t2].x  + y5 * Q._point[t2].x;

			x7 = x7 / 1.0 / (y5 - P._point[t2].y);
			s1 --;
		}
		else if( P._point[t1].y <= P._point[s1].y && P._point[t1].y <= Q._point[t2].y && P._point[t1].y <= Q._point[s2].y )
		{
			y2 = y3 = y6 = y7 = P._point[t1].y;
			x3 = P._point[t1].x;
			x2 = - y2 * P._point[s1].x + x0  * y2 + y0 * P._point[s1].x  - x0 * P._point[s1].y;

			x2 = x2 / 1.0 / (y0 - P._point[s1].y);
			x6 = - x4 * Q._point[s2].y + x4  * y6 - y6 * Q._point[s2].x  + y4 * Q._point[s2].x;

			x6 = x6 / 1.0 / (y4 - P._point[s2].y);
			x7 = - x5 * Q._point[t2].y + x5  * y7 - y7 * Q._point[t2].x  + y5 * Q._point[t2].x;

			x7 = x7 / 1.0 / (y5 - P._point[t2].y);
			t1 ++;
		}
		else if( Q._point[s2].y <= P._point[s1].y && Q._point[s2].y <= P._point[t1].y && Q._point[s2].y <= Q._point[t2].y )
		{
			y2 = y3 = y6 = y7 = Q._point[s2].y;
			x6 = Q._point[s2].x;
			x3 = - x1 * P._point[t1].y + x1  * y3 - y3 * P._point[t1].x  + y1 * P._point[t1].x;

			x3 = x3 / 1.0 / (y1 - P._point[t1].y);
			x2 = - y2 * P._point[s1].x + x0  * y2 + y0 * P._point[s1].x  - x0 * P._point[s1].y;

			x2 = x2 / 1.0 / (y0 - P._point[s1].y);
			x7 = - x5 * Q._point[t2].y + x5  * y7 - y7 * Q._point[t2].x  + y5 * Q._point[t2].x;

			x7 = x7 / 1.0 / (y5 - P._point[t2].y);
			s2 --;
		}
		else
		{
			y2 = y3 = y6 = y7 = P._point[t2].y;
			x7 = P._point[t2].x;
			x3 = - x1 * P._point[t1].y + x1  * y3 - y3 * P._point[t1].x  + y1 * P._point[t1].x;

			x3 = x3 / 1.0 / (y1 - P._point[t1].y);
			x2 = - y2 * P._point[s1].x + x0  * y2 + y0 * P._point[s1].x  - x0 * P._point[s1].y;

			x2 = x2 / 1.0 / (y0 - P._point[s1].y);
			x6 = - x4 * Q._point[s2].y + x4  * y6 - y6 * Q._point[s2].x  + y4 * Q._point[s2].x;

			x6 = x6 / 1.0 / (y4 - P._point[s2].y);
			t2 ++;
		}

		temp = (x7 - x6 + x5 - x4 + x3 - x2 + x1 - x0) * (y7 - y0) / 2.0;

		if(fabs(temp - Volume)>1e-7)
		{
			double l = (x7 - x6 + x3 - x2) * (x7 - x6 + x3 - x2) - (x5 - x4 + x1 - x0) * (x5 - x4 + x1 - x0);
			double m = (x5 - x4 + x1 - x0);
			double n = 4 * Volume * temp;
			high += (- m + sqrt (m * m + l * n)) / l;
		}
		else
		{
			Volume -= temp;
			high += y3 - y0;
		}

		x0 = x2, y0 = y2;
		x1 = x3, y1 = y3;
		x4 = x6, y4 = y6;
		x5 = x7, y5 = y7;

	}

	return high + P._point[P._min].y;
}

int main()
{
	Digra_2 P, Q;

	int count;
	double Volume, high;

	while(cin >> count)
	{
		while( count -- && cin >> Volume && Volume)
		{
			Init(P);
			Init(Q);

			if(P._point[P.end_min].y <= Q._point[Q._min].y)
			{
				high = Pour(P, Volume);
			}
			else if(Q._point[Q.end_min].y <= P._point[P._min].y)
			{
				high =Pour(Q, Volume);
			}
			else if(P._point[P._min].y <= Q._point[Q._min].y)
			{
				high =Pour(P, Q, Volume);
			}
			else
			{
				high =Pour(Q, P, Volume);
			}

			cout << fixed << setprecision( 3 ) << high << endl;
		}

	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator