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