Страница 2 Python3: TLE #8 Python2: AC 0.8 sec Code is the same. (Pseudo-vector product) Edited by author 28.04.2017 17:08 Edited by author 19.01.2016 11:10 try this one 7 1 1 2 2 4 3 5 3 7 2 9 0 5 7 answer is ccw who can explain this statement? It confused me very much.. :/ Calculate the signed area of the polygon... Firstly, find any point with largest X (or Y) coordinate and then compute the cross product of two vectors formed by two adjacent points and this point. You need to find a point with largest X (or Y) coordinate as the polygon is not convex. input: 4 3 2 2 2 2 3 0 0 output: ccw first i WA#10 and when i notice to this test i got AC. sorry for my poor english, i hope this test help you. GOOD LUCK ! Страница 1 // zadachki.cpp: определяет точку входа для консольного приложения. // #include <iostream> #include "vector" using namespace std; int main() { int n; double t; vector<double>x; vector<double>y; cin>>n; for(int i=0; i<n; i++) { cin>>t; x.push_back(t); cin>>t; y.push_back(t); } for(int i=0; i<n;i++) { double m=((x[(i+1)%n]-x[i])*(y[(i+2)%n]-y[(i+1)%n])-(x[(i+2)%n]-x[(i+1)%n])*(y[(i+1)%n]-y[i])); if (m>0) {cout<<"ccw"; return 0;} if (m<0) {cout<<"cw"; return 0;} } return 0; } WHY? Can anyone let me 7 test... sorry... 10 test Edited by author 07.11.2010 16:53 C++ : #include "iostream" using namespace std; int main() { int n; double X1, Y1, X2, Y2; cin >> n >> X1 >> Y1 >> X2 >> Y2; double x1 = X1, y1 = Y1, x2 = X2, y2 = Y2, x3, y3, ans = 0; for(int i = 1; i <= n - 2; i++) { cin >> x3 >> y3; ans += x2 * (y3 - y1) + x3 * (y1 - y2) + x1 * (y2 - y3); x1 = x2; y1 = y2; x2 = x3; y2 = y3; } ans += x2 * (Y1 - y1) + X1 * (y1 - y2) + x1 * (y2 - Y1); x1 = x3; y1 = y3; x2 = X1; y2 = Y1; ans += x2 * (Y2 - y1) + X2 * (y1 - y2) + x1 * (y2 - Y2); ans > 0 ? cout << "ccw" : cout << "cw"; return 0; } Pascal: {$R-} Var X, Y: Array[1..200002] Of Extended; i, n: LongInt; Ans: Extended; Function AL(Const x1, y1, x2, y2, x3, y3: Extended): Extended; Begin AL := x2 * (y3 - y1) + x3 * (y1 - y2) + x1 * (y2 - y3); End; { AL } Begin ReadLn(n); For i := 1 To n Do ReadLn(X[i], Y[i]); X[n + 1] := X[1]; Y[n + 1] := Y[1]; X[n + 2] := X[2]; Y[n + 2] := Y[2]; ans := 0; For i := 1 To n Do ans := ans + AL(X[i], Y[i], X[i + 1], Y[i + 1], X[i + 2], Y[i + 2]); If ans < 0 Then Write('cw') Else Write('ccw'); End. Edited by author 25.08.2010 18:34 9 0 0 1 0 1 1 2 2 3 1 3 0 4 0 4 3 0 3 answer: ccw Edited by author 31.07.2010 19:05 I know AC solution that counts number of cw and ccw moves from point i to i+1 seen from the first point. Here is the test on which this AC solution answers cw but correct answer is ccw. 17 0 0 10 0 10 10 11 10 11 9 11 8 11 7 11 6 11 5 11 4 11 3 11 2 11 1 11 0 12 0 12 11 0 11 I'm agree with you. Edited by author 22.03.2010 08:38 I'm sorry. I find my mistake/ I got AC after used double (instead long long). Then I wrote code: scanf("%d", &N); for (int i = 0; i < N; ++i) { P[i].x = ReadAndCheck(); P[i].y = ReadAndCheck(); } double ReadAndCheck() { char s[100]; scanf("%s", s); for (int i = 0; s[i]; ++i) Assert(isdigit(s[i])); double r; sscanf(s, "%lf", &r); return r; } To all appearences Assert was called (4 test). I've got AC reading ints. Please change Assert(isdigit(s[i])); to Assert(isdigit(s[i]) || s[i] == '-'); and test if Assert will be called. I've got AC reading ints. Please change Assert(isdigit(s[i])); to Assert(isdigit(s[i]) || s[i] == '-'); and test if Assert will be called. I sent cw-answers for all test and ccw. The result was WA1 for both. What does it mean? I sent 2 ways of right design for my tests befor it. I sent with \n and without/ Please cheak tests. I can't find my mistake. Can you sent me test#2 to <<mihran91@mail.ru>>? this is my code # include <iostream.h> # include <math.h> main () { double dx[50001],dy[50001]; int i,n; double x0,y0,xk,yk,x1,y1; cin>>n; for(i=0;i<n;i++) cin>>dx[i]>>dy[i]; dx[n]=dx[0];dy[n]=dy[0]; xk=0.5*(dx[0]+dx[1]); yk=0.5*(dy[0]+dy[1]); x1=dx[0]-dx[1]; y1=dy[0]-dy[1]; y0=yk+0.00000001; x0=(xk*x1-y0*y1+yk*y1)/x1; double ma,mb,a[2],b[2],det,otv=0; A: for(i=0;i<n;i++) { a[0]=dx[i]-x0; a[1]=dx[i+1]-x0; b[0]=dy[i]-y0; b[1]=dy[i+1]-y0; ma=sqrt(a[0]*a[0]+b[0]*b[0]); mb=sqrt(a[1]*a[1]+b[1]*b[1]); det=a[0]*b[1]-b[0]*a[1]; if(det>0) otv+=acos((a[0]*a[1]+b[0]*b[1])/(ma*mb)); else otv-=acos((a[0]*a[1]+b[0]*b[1])/(ma*mb)); } if(fabs(fabs(otv)-6.28318530717)>0.00001) { otv=0; y0=yk-0.00000001; x0=(xk*x1-y0*y1+yk*y1)/x1; goto A; } if(otv<0) cout<<"cw"; else cout<<"ccw"; return 0; } Don't write such message to admins. I think they don't mail to you anything. Why WA1 ??? Even if replace cw and ccw. The same with lowermost (3) point. Help me pleace. What with my output? #include <iostream> using namespace std; int main() { int n; int x1, y1; int x, y; int Oldx, Oldy; cin >> n; cin >> x1 >> y1; Oldx=x1; Oldy=y1; double sum = 0; for(int i=2; i<=n; ++i) { scanf("%d %d", &x, &y); sum += (Oldx*(double)y-x*(double)Oldy); Oldx=x; Oldy=y; }
sum += (x*(double)y1-x1*(double)y); if(sum) cout << "cw"; else cout << "ccw"; return 0; } #include <iostream> using namespace std; int main() { int N,z=0,z1,z2; int x1,y1,x2,y2,x3,y3; cin >> N >> x1 >> y1 >> x2 >> y2; N-=2; int xx1=x1,yy1=y1; x1 =x2 - x1; y1 =y2 - y1; int xx=x1,yy=y1; while (N--) { cin >> x3 >> y3; z1 =x3 - x2; z2 =y3 - y2; z+= x1*z2-z1*y1; x1 = z1; y1 = z2; x2 = x3; y2 = y3; } z1 = xx1-x3; z2 = yy1-y3; z+= z1*yy-z2*xx; if (z<0) cout << "cw"; else cout << "ccw"; return 0; } Edited by author 24.08.2007 15:33 I think you've forgotten about the 1st and nth points) And also you should write something like z += ... to count the total direction) Good Luck!)) Edited by author 24.08.2007 08:57 I had the same problem. But when I replaced "int" with "double", I've got AC. Just try to calculate next expression: 50000*50000 - 50000*(-50000) = ??????????? Numbers in exponential notation were deleted from the tests. All coordinates now are integers from -50000 to 50000. New tests were added and the problem was rejudged. Numbers in exponential notation were deleted from the tests. What is the reason for this? It was such an exciting adventure to solve this problem in Java! java.util.Scanner is too slow, java.io.StreamTokenizer with standard settings does not understand exponential notation. That was fantastic! I don't know any other problem that uncovers fact that StreamTokenizer does not support exponential notation. It is very big loss that coordinates are integer now. How stupid I am. At first I think I should use "bignum",so I kept coding and coding for about two hours. But I found that it's so complex. So I stopped and start reading the board. Oh my dear,I realized that the "double"'s range is about from -3e+302 to +3e+302. So everybody who see this don't try to use "bignum",double is enough. Double can of course get AC... But the tests seem to be really weak (the so-called 2 or 3 coords algorithms are actually wrong). But the correct algorithm is not hard to write. Why not do it in this way? We take the lowermost point - O. The previous point - A, and following - B. Let q = cos (corner between AO and axis OX) r = cos (corner between BO and axis OX) If q < r then ccw else cw I got AC!!! Simple but wrong! Simple test: 3 4 4 1 1 3 5 Your answer is ccw, but correct cw. Another proof that timus test are weak :( The method which find the lowermost point is right... But don't use cos & sin, think another way :) MY! solution is simple) only 6 actions for every Vertex. Don't use sin or cos .... 3 4 4 1 1 3 5=cw?Have you ever seen any clocks? |
|