| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
why always WA?#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator