The first observation to make is that 4 edges can make a polygon of perimeter N iff their lengths are all in the range 1..n/2. Then the problem becomes counting the number of ways 4 integers in the range 1...k sums to N, which can be done with dynamic programming.
The DP state is num[i,s], which represents the number of ways of making a sum of s using i such numbers. Then the base case is when i=0, where num[0,0]=1 and num[0,s']=0.
Now for the transition, suppose the ith number of x, then we have num[i-1,s'-x] contributing to num[i,s']. So the transition is num[i,s']=sum(1<=x<=min(s',[n/2]),num[i-1,s'-x]. Computing this naively using a for loop gives an O(N^2) algorithm, and any type of optimization by precomputing partial sums or two pointer walks would give a O(N) algorithm.
Below is Jaehyun Park's solution:
#include<stdio.h> long long d[3000]; int main() { int n; FILE *ifp=fopen("quad.in", "r"), *ofp=fopen("quad.out", "w"); d[5]=4; for(n=7;n<=2500;n+=2) d[n]=d[n-2]*(n+1)/(n-5); for(n=6;n<=2500;n+=2) d[n]=d[n-1]+(n-1)/2; fscanf(ifp, "%d", &n); fprintf(ofp, "%lld\n", d[n]); fclose(ifp); fclose(ofp); return 0; }