# UVa 10079

## Summary

Given the number of straight cuts you can make on a pizza, find the maximum number of pieces in which the pizza can be divided.

## Explanation

If we make no cuts at all, we still have the whole pizza to eat. Hence ${\displaystyle A(0)=1}$. Each new cut can possibly intersect all the previous cuts. It means that After ${\displaystyle n-1}$ lines have been drawn, the nth line can intersect each of these, so it has ${\displaystyle n-1}$ intersections, and hence ${\displaystyle n}$ new regions, so the recurrence we get is ${\displaystyle A(n)=A(n-1)+n;\ A(0)=1}$. Solving this recurrence gives the formula ${\displaystyle A(n)=n+(n-1)+(n-2)+...2+1+A(0)}$ and hence ${\displaystyle A(n)=n(n+1)/2+1}$.

## Implementation

• Use 64-bit integers (long long in C++) to avoid overflow.

```0
5
10
210000000
-100
```

## Output

```1
16
56
22050000105000001
```