Show all threads Hide all threads Show all messages Hide all messages |
Please give me tests. WA15. | Vlad Mikhalev | 1246. Tethered Dog | 27 Sep 2018 10:29 | 1 |
|
Hint | KALO | 1246. Tethered Dog | 25 Jun 2018 12:52 | 2 |
Hint KALO 21 Nov 2010 18:23 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. |
Try to use Python2.7 if you have Python3.4 TLE | Mahilewets | 1246. Tethered Dog | 28 Apr 2017 17:04 | 1 |
Python3: TLE #8 Python2: AC 0.8 sec Code is the same. (Pseudo-vector product) Edited by author 28.04.2017 17:08 |
No subject | Felix_Mate | 1246. Tethered Dog | 18 Jan 2016 22:42 | 1 |
Edited by author 19.01.2016 11:10 |
WA7 = integer overflow | Otrebus | 1246. Tethered Dog | 4 Sep 2015 16:30 | 1 |
|
in case of WA#11 | nikitaevg | 1246. Tethered Dog | 28 Aug 2015 18:19 | 1 |
try this one 7 1 1 2 2 4 3 5 3 7 2 9 0 5 7 answer is ccw |
statement | Mamuka Sakhelashvili [Freeuni] | 1246. Tethered Dog | 22 Feb 2014 19:52 | 1 |
statement Mamuka Sakhelashvili [Freeuni] 22 Feb 2014 19:52 who can explain this statement? It confused me very much.. :/ |
test 10 | hoan | 1246. Tethered Dog | 3 Oct 2011 19:02 | 2 |
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 ! |
Why WA#10 | Andy_spb | 1246. Tethered Dog | 7 Nov 2010 16:52 | 2 |
// 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 |
WA17 Who can help me? | Artem Ladik | 1246. Tethered Dog | 25 Aug 2010 18:31 | 1 |
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 |
IMHO, good test for convex hull solutions | Alexander Samal | 1246. Tethered Dog | 31 Jul 2010 19:03 | 1 |
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 |
My solution is very simple!!! | Виктор (marilyn_manson@bk.ru) | 1246. Tethered Dog | 13 Jul 2010 17:48 | 5 |
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? |
Weak tests | Fyodor Menshikov | 1246. Tethered Dog | 22 Mar 2010 08:37 | 3 |
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/ |
Changes in problem 1246 (+) | Sandro (USU) | 1246. Tethered Dog | 11 Jan 2009 21:11 | 2 |
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. |
The coordinates are a pair of integers .... It's right ? | ryu | 1246. Tethered Dog | 11 Jan 2009 15:04 | 4 |
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. |
To Admins!!! | Desperados[KhAI] >> Starov_Lesha | 1246. Tethered Dog | 26 Jul 2008 00:29 | 2 |
To Admins!!! Desperados[KhAI] >> Starov_Lesha 25 Jul 2008 18:01 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. |
To Admins | Mihran Hovsepyan {2 kurs of <RAU>} | 1246. Tethered Dog | 18 Jul 2008 15:25 | 2 |
To Admins Mihran Hovsepyan {2 kurs of <RAU>} 18 Jul 2008 15:12 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. |
cw or ccw => Wrong Answer 1 ??? | Desperados[KhAI] >> Starov_Lesha | 1246. Tethered Dog | 9 Jun 2008 22:17 | 1 |
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; } |
please give me a test, I have WA 15 =) | Samsonov Ivan (Rybinsk SAAT) | 1246. Tethered Dog | 22 Nov 2007 21:53 | 3 |
#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) = ??????????? |
200000 for 1 second? Help me, please! | Danilchenko Anton | 1246. Tethered Dog | 11 Jan 2007 16:13 | 10 |
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. > Speed aa 3 Apr 2003 20:15 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 |