Блог пользователя i_am_eating_wa_and_tle

Автор i_am_eating_wa_and_tle, история, 7 недель назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор i_am_eating_wa_and_tle, история, 9 месяцев назад, По-английски

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
}

Полный текст и комментарии »

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

Автор i_am_eating_wa_and_tle, история, 6 лет назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор i_am_eating_wa_and_tle, история, 6 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор i_am_eating_wa_and_tle, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

Автор i_am_eating_wa_and_tle, 7 лет назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

Автор i_am_eating_wa_and_tle, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор i_am_eating_wa_and_tle, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

Автор i_am_eating_wa_and_tle, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор i_am_eating_wa_and_tle, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

Автор i_am_eating_wa_and_tle, история, 8 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

Автор i_am_eating_wa_and_tle, история, 8 лет назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится