| Submit | All submissions | Best solutions | Back to list |
DIG - DIAGONAL |
You are a given a n sided convex polygon. Find total number of intersections of all diagonals.
Assume that all the intersection points are different.
If in case answer exceeds 10^9 + 7 , take modulo 10^9 + 7
1<=n<=10^8
Input
First Line : T (number of test cases)
Next T line will contain N number of vertices
Output
Number of intersections of diagonals as specified.
Example
Input:
2
4
5
Output:
1
5
| Added by: | praveen123 |
| Date: | 2012-08-01 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | general problem |
hide comments
|
|||||
|
2017-07-19 14:05:03
Use 24*10000000007L for taking modulo in c ,lest u will get stroked! |
|||||
|
2016-07-06 14:02:05
derive formula and then modular division/multiplication AC |
|||||
|
2016-07-05 15:23:08
easy if u knw the formula!! formula derivation requires some work!! i did dat while my jee prep.(chp = P& C) :-P glad i remember it till now :-) AC 1 go:-) |
|||||
|
2014-05-29 22:50:01 Francky
@candide : Suppose for a while «diagonal means unbounded», what would be the interest to specify "convex" ? ans=NULL. Now suppose the opposite, "convex" makes sens in the problem statement. In this condition, we can honestly assert «here, diagonal means bounded». It's always good to be as precise as possible. Many thanks to candide for his rigorous catch. Here the description seems robust enough. |
|||||
|
2014-05-29 22:12:51 candide
@flago Convexity is not sufficient. Specifically, depends on what you mean by "Diagonal": is it a "line" (non bounded region) or a "segment line" (bounded region). |
|||||
|
2014-05-28 15:35:05 Flago
@candide : given a *convex* polygon, so it is specified. |
|||||
|
2014-04-26 08:42:47 candide
Interesting question, not tutorial at all. But problem statement is ambiguous : the fact that diagonal intersections to be INSIDE the polygon is not specified. There is a similar formula for the case where you don't care about the position of the intersection. Moreover, examples are poorly chosen for not allowing to discriminate the two cases. Another remark : cases n=1 and n=2 are meaningless. Last edit: 2014-04-26 08:44:21 |
|||||
|
2012-08-09 17:35:41 Francky
Arghh, convex is very important, I first solved for diagonal lines of any polygon. |
|||||
|
2012-08-08 13:56:53 :D
I didn't find it trivial just easy. Is it easy because there's a know formula for it or is it really so basic to construct the formula on your own? |
|||||
|
2012-08-02 10:03:27 devu
It is not a tutorial problem,nice concept behind it,nice problem |
|||||
RSS