SPOJ MPOLI - Codeforces

→ Pay attention

Before contest
Refact.ai Match 1 (Codeforces Round 985)
4 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

PraveenDhinwa's blog

SPOJ MPOLI

By PraveenDhinwa, 13 years ago, In English

Hi guys ,,, Could anybody help me How to solve http://www.spoj.pl/problems/MPOLY/ . I tried to relate it with convex Hull ,, But It did not work . There is a codeforces blog on dp problems ,which suggests it to be a geometry dp problem ,, Any hints please!!!!!! Any kind of help will be appreciated . Thank you.

PraveenDhinwa
13 years ago
2

Comments (2)

Write comment?

goo.gl_SsAhv

13 years ago, # |

← Rev. 3 →

1) consider point (0, 0) as center of our plane.
2) sort points by angle
3) add point (0, 0) at first position of array Let DP(a, b) — maximal possible number of points which can be added. (a < b)
(small letters are indexes, while capital letters are points, with corresponding indexes)
We can add point C if and angle Alpha ABC is 0 < Alpha < 180.
1) if we cannot add any point we have to add point (0, 0) if we can, otherwise answer is -infinity
2) try to add any point C, such that b < c and chose maximal anser pseudocode:

DP(a, b)
{
  if (calculated[a][b])
    return dp[a][b];
  res = -infinity;
  if (Can(p[a], p[b], Point(0, 0))) res = 0;
  for (c = b + 1; c < n; c++)
    if (Can(p[a], p[b], p[c]))
      res = max(res, DP(b, c));
  calculated[a][b] = true;
  dp[a][b] = res;
}

→ Reply

anh1l1ator

8 years ago, # ^ |

← Rev. 3 →

How do you sort by angle? I am trying to solve it this way! I am getting WA all the time.

What am I doing wrong?
Than n is actually '\n'. I don't know how to print it using some escape sequence here.

My Code

#include<bits/stdc++.h>
using namespace std;
typedef pair < int , int > Point;

bool cmp(Point &A, Point &B){
    if(B.first*A.second!=A.first*B.second)
        return (A.second*1.0)/A.first>(B.second*1.0)/B.first;
    else if(A.first!=B.first)
        return A<=B;
    else
        return A.second>B.second;
}

int dp[101][101];
const int INF = (int)1e9;
Point create(Point B , Point A){return {A.first-B.first,A.second-B.second};}
int cross(Point A,Point B){return A.first * B.second - B.first * A.second;}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    string S;
    while(cin>>S)
    {
        int N , i , j ;
        cin>>N;
        vector < Point > A(N+1);
        for(i=1;i<=N;++i)
            cin>>A[i].first>>A[i].second;
        sort(A.begin()+1,A.end(),cmp);
        A[0] = {0,0};
        for(i=0;i<=N;++i)
            for(j=0;j<=N;++j)
                dp[i][j] = -INF;
        int ans = 3;
        for(i=1;i<=N;++i)
        {
            dp[i][0] = 2;
            for(j=1;j<=i-1;++j)
            {
                for(int k=0;k<=j-1;++k)
                    if(cross(create(A[k],A[j]),create(A[j],A[i]))<0)
                        dp[i][j] = max(dp[i][j] , dp[j][k]+1);
                
                if( cross( create(A[j],A[i]) , create(A[i],A[0])  )<0)
                        ans = max(ans , dp[i][j]);
            }
        }
        cout<<"POLYGON.OUTnn";
        cout<<ans<<'n';
    }
    cout<<endl;
    return 0;
}

→ Reply