I have found this tutorial on topcoder Geometry Concept part 1.

In the last section of the tutorial it discusses about area of a polygon. I have took the code and ran it in my IDE but it seems that it give me area = 0 for this coordinates p = {{-1, -1}, {1, 1}, {1, -1}, {-1, 1}}.

What am I missing?

full code

#include <bits/stdc++.h>

using namespace std;

int main() {
    vector<vector<double>> p = {{-1, -1}, {1, 1}, {1, -1}, {-1, 1}};
    double area = 0;
    int N = p.size();
    //We will triangulate the polygon
    //into triangles with points p[0],p[i],p[i+1]

    for (int i = 1; i + 1 < N; i++) {
      double x1 = p[i][0] - p[0][0];
      double y1 = p[i][1] - p[0][1];
      double x2 = p[i + 1][0] - p[0][0];
      double y2 = p[i + 1][1] - p[0][1];
      double cross = x1 * y2 - x2 * y1;
      area += cross;
    }
    cout << abs(area / 2.0) << endl;
    return 0;
}

As far as I know stack.push() have a O(1) time complexity but is it actually correct if I use a stack of string.

stack<string> stringStack;
string inputString;
while(cin >> inputString) {
    stringStack.push(inputString); // what is the time complexity of this line
}

Problem Link: LightOJ 1407

PDF LINK: click here

How to solve this problem. I know the basic algorithm of solving 2SAT problem. In the basic algorithm for (Xi ∨ Yi) the implications are

1. ¬Xi => Yi

2. ¬Yi => Xi

But here in this problem I can't figure out the implications of the relation stated in the problem. Can you please help me Solve this problem???

problem link: http://lightoj.com/volume_showproblem.php?problem=1308

For PDF click here

How to solve this problem? I have tried much but failed everytime.

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1077

For pdf Click here

As the problem says to find the lattice points from (Ax, Ay) to (Bx, By).My idea was to find the number of solutions of the equation x * (Ay-By) — y * (Ax-Bx) = Ax * ( Ay-By) — Ay * (Ax-Bx) which is basically Extended Euclid. I got WA so many times. And after that I found this. But I can't understand why this problem can't be solved using Extended Euclid. Can anybody Please explain ? After solving this problem I thought either I don't understand Extended Euclid or there is a bug in my code.

Is it possible to find the last two non-zero digits of a factorial of a number ranges from 1 to (10^100)! ??????

UPD:Got AC

PDF LINK: http://lightoj.com/volume_showproblem.php?problem=1138&language=english&type=pdf Problem link: http://lightoj.com/volume_showproblem.php?problem=1138

I think the solution is the number of 5s as prime factor in N! But how to calculate them faster.

problem link: http://lightoj.com/volume_showproblem.php?problem=1098

PDF Link: lightoj.com/volume_showproblem.php?problem=1098&language=english&type=pdf

I think this problems solution is Summation of ((floor(N/i) — 1) * i) .But n is 10^9. It will definately get TLE if I precalculate or use loop.I think there exist something that I do not know yet.Please help me solve this problem. If I need to learn any theory/algorithm to solve this problem please mention it.

Thank you very much.

Problem link: http://lightoj.com/volume_showproblem.php?problem=1359

For PDF click here

I think this is a very interesting problem. It is a LightOJ problem and catagorized under LCA/RMQ. What can be the solution idea for this problem? I can't find one, please help.

Hello everyone

I was trying to solve this problem. I have tried to solve this problem about 18 hours but I failed.I think it can be solved using k-th shortest path algorithm but I can't find an understandable article on k-th shortest path algorithm.Can anyone please explain the k-th shortest path finding algorithm. I know the Dijstra's algorithm. Also, if it can be solved using other algorithm then please help me to know the algorithm.

Geometry is the most terrible word in my life. But now, I want to get rid of this terror. Please suggest me some beginner books on geometry.

In the Editorial "Divide by Zero and Codeforces Round #399 (Div. 1+2, combined)" the problem setter said PROBLEM B can be solved easily by using DIVIDE AND CONQUER strategy. How to learn this strategy????