Calculate the signed area of the polygon...

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

nt

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...

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!!!

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

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.

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 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;
}

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

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.