Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Please give me tests. WA15. | Vlad Mikhalev | 1246. Собака на привязи | 27 сен 2018 10:29 | 1 |
|
Hint | KALO | 1246. Собака на привязи | 25 июн 2018 12:52 | 2 |
Hint KALO 21 ноя 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. Собака на привязи | 28 апр 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. Собака на привязи | 18 янв 2016 22:42 | 1 |
Edited by author 19.01.2016 11:10 |
WA7 = integer overflow | Otrebus | 1246. Собака на привязи | 4 сен 2015 16:30 | 1 |
|
in case of WA#11 | nikitaevg | 1246. Собака на привязи | 28 авг 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. Собака на привязи | 22 фев 2014 19:52 | 1 |
statement Mamuka Sakhelashvili [Freeuni] 22 фев 2014 19:52 who can explain this statement? It confused me very much.. :/ |
test 10 | hoan | 1246. Собака на привязи | 3 окт 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. Собака на привязи | 7 ноя 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. Собака на привязи | 25 авг 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. Собака на привязи | 31 июл 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. Собака на привязи | 13 июл 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. Собака на привязи | 22 мар 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. Собака на привязи | 11 янв 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. Собака на привязи | 11 янв 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. Собака на привязи | 26 июл 2008 00:29 | 2 |
To Admins!!! Desperados[KhAI] >> Starov_Lesha 25 июл 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. Собака на привязи | 18 июл 2008 15:25 | 2 |
To Admins Mihran Hovsepyan {2 kurs of <RAU>} 18 июл 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. Собака на привязи | 9 июн 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. Собака на привязи | 22 ноя 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. Собака на привязи | 11 янв 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 апр 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 |