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. 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.. :/ 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 ! // 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 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? 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/ 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. 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) = ??????????? My program work about 6.8 second on full test on P166. But 6.2 second of this time is a reading data (testing from hard disk not from memory). How can I read more then 200000x2x10=4000000 bytes for 1 second? Though test is all in memory (I think), I belive that scaning data to float format is very hard operation. I used 'scanf' function. Give me good advice please. here they've quite fast computers so don't worry if you have a good solution !!!. I've solved it just by analyzing every point one by one while reading them. After I'd solved it, I realised that they have only tests to which answer is 'ccw' so they didn't strained themselves ;P If you experience any further problems just ask ! Good luck !!! > here they've quite fast computers so don't worry if you have a good > solution !!!. I've solved it just by analyzing every point one by one > while reading them. After I'd solved it, I realised that they have > only tests to which answer is 'ccw' so they didn't strained > themselves ;P > > If you experience any further problems just ask ! > > Good luck !!! I've got time limit 2 times. > I've got time limit 2 times. > No, their computers are slow, I think. I have a solution worked about 2.4 sec(not this problem, and I have a watch to calculate the time) on my computer(Duron 800) but the judge said I worked 3.1 sec! Why Time Limit? I tried to use double, iostream. How to solve easier O(N)? [code deleted] Edited by moderator 11.01.2007 16:20 How You get this solution. Explain him, please. Moderators, please remove the code from this branch of the forum. Why Time Limit? I tried to use double, iostream. How to solve easier O(N)? [code deleted] Edited by moderator 11.01.2007 16:21 |
|