Can read about orientation here Idea comes from the slope comparison. #include <iostream> #include <algorithm> #include <cstdio> #include <vector> #include <cmath> using namespace std; struct point{ double x,y; }; vector<point>pp; double area(int n,vector<point> arr) { double ans = 0.0; for(int i=0;i<n;i++) { ans += (arr[i].x*arr[(i+1)%n].y – arr[i].y*arr[(i+1)%n].x); } return fabs(ans/2.0); } int checkCross(point p, point
Category: Programming Problem
10359
#include <iostream> #include <cstdio> using namespace std; int f[260][1000]; int length[260]; void init() { for(int i=0;i<260;i++) { length[i]=0; for(int j=0;j<1000;j++) f[i][j]=0; } } int main() { int n,j,cary,begn; init(); f[0][0]=1; f[1][0]=1; for(int i=2;i<260;i++) { cary=0; for(j=0;j<1000;j++) { f[i][j]=(f[i-1][j]+2*f[i-2][j]+cary)%10; cary=(f[i-1][j]+2*f[i-2][j]+cary)/10; } if(cary!=0) f[i][j]=cary; } while(scanf("%d",&n)!=EOF) { for(int i=999;i>=0;i–) { if(f[n][i]) { begn=i; break; } } for(int
10918
Using DP #include <iostream> #include <cstdio> #include <cstring> using namespace std; int f[35]; int g[35]; int main() { for(int i=0;i<35;i++) f[i]=g[i]=0; f[0]=1; f[1]=0; g[0]=0; g[1]=1;//one missing cornered rect of size 3×1 for(int i=2;i<35;i++) { f[i]=f[i-2]+2*g[i-1];//if last column are 3 of (2×1) OR one vertical 2×1(and removing that will leave one missing cornered ractngle of 2
10363
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int xwin[8]; int owin[8]; /* 1 XX. XX. OOO */ string str[4]; bool rowcheck(char c) { for(int i=0;i<3;i++) { if(str[i][0]==str[i][1] && str[i][0]==str[i][2] && str[i][0]==c) return 1; } return 0; } bool diagncheck(char c) { if(str[0][0]==str[1][1] && str[1][1]==str[2][2] && str[1][1]==c) return 1; if(str[0][2]==str[1][1] && str[1][1]==str[2][0] && str[1][1]==c)
1099
DP+bitmask #include <iostream> #include <cstdio> #include <vector> #include <queue> #include <sstream> #include <string> #include <cstring> //#include <fstream> #include <cmath> using namespace std; int sizes[16]; int n; int row,col; int sum[32780];//1<<n-1=state int dp[105][32780];//[width or height][state] int _min(int a,int b) { if(a<b) return a; return b; } //karnighan's bit count algorithm int check(int x) { int res=0;
10874
#include <iostream> #include <cstdio> #include <queue> #include <sstream> #include <string> #include <cstring> #include <cmath> #define ll long long #define INF 500000000 using namespace std; struct point{ int left; int right; }; point arr[20005]; ll dp[20005][2]; void init() { for(int i=0;i<20005;i++) for(int j=0;j<2;j++) dp[i][j]=INF; } ll _min(ll a,ll b) { if(a<b) return a; return b; }
10898
#include <iostream> #include <cstdio> #include <queue> #include <sstream> #include <string> #include <cstring> #include <cmath> #define INF 100000000 #define ll long long using namespace std; int MX,cnt; int Item,Combo,noOfOrder; ll bestDp[1000000]; ll packPrice[1000000]; int packages[20]; void init() { cnt=0; for(int i=0;i<1000000;i++) { bestDp[i]=INF; packPrice[i]=0; } for(int i=0;i<20;i++) packages[i]=0; } ll _min(ll a,ll b) { if(a<b) return
10849
two positions of a NxN chess board can be connected by pawns move(diagonally) iff both of them are on black/white position, this can be checked by checking the pair. if both of the x,y (start position ) and X,Y(end position) are odd,odd or even,even then they can be connected or both of the pair are
10337
It’s a bottom up dp approach. #include <iostream> #include <cstdio> #include <queue> #include <sstream> #include <string> #include <queue> #include <vector> #include <cstring> #include <algorithm> #include <cmath> #define INF 100000000 using namespace std; vector<int> vb[11]; vector<int> v; int dp[11][1010]; void init() { for(int i=0;i<11;i++) { vb[i].clear(); for(int j=0;j<1010;j++) { dp[i][j]=-1; } } } int _min(int a,int
11450
It’s a bottom up approach. #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <vector> #define INF 100000000 using namespace std; int MX; vector<int> vb[21]; int dp[201][21]; void init() { for(int i=0;i<21;i++) vb[i].clear(); MX = INF; for(int i=0;i<201;i++) for(int j=0;j<21;j++) { if(j==0) dp[i][j]=0; else dp[i][j]=-1;//not solved } } int _max(int a,int b) {