Description

In the homework, you have learned the basic operations and simple applications of vectors. Now, let's do a more powerful function:
Given the vertices of a polygon in order (may be clockwise or counterclockwise), please calculate its area.

The provided header file is very similar to the one used in the homework. However, you can choose not to implement some of the functions if you think they are not needed. The member functions of Vector are as follows:

• Vector operator+(const Vector &rhs) const: Add two vectors.
• Vector operator-(const Vector &rhs) const: Subtract self vector by another vector.
• double operator*(const Vector &rhs) const: Calculate the dot product of two vectors.
• double operator^(const Vector &rhs) const: Calculate the cross product of two vectors.
• double area(const Vector &rhs) const: Calculate the area of the triangle formed by two vectors.
• Vector projection(const Vector &rhs) const: Calculate the projection of self vector on another vector.

The only function you need to implement is double area(Vector v[], int n). It should return the area of the polygon whose vertices are stored in the array v[]. The vertices are given in (counter)clockwise order, and the last vertex is connected to the first vertex. The parameter n is the number of vertices.

Warning: You should use C++11 or later versions, or else you will get Compile Error! reason

Example

For the sample input, the polygon should look like this.

Input

The first line contains an integers $n$, which represents the number of points.
Each of the next $n$ lines contains two integers $x_i, y_i$, represent the point's position.

$n$
$x_1 \quad y_1$
$x_2 \quad y_2$
$\vdots$
$x_n \quad y_n$

Constraints

• $-10^6 \le x_i, y_i \le 10^6$
• For testcase 1, 2, 5, 6, it's guaranteed that the origin $(0, 0)$ is inside the polygon.
• For testcase 1, 2, 3, 4, $3 \le n \le 10^3$
• For testcase 5, 6, 7, 8, $4 \le n \le 10^5$

Output

Print the area of the polygon, whose vertices are the input points.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14276.cpp

Partial Judge Header

14276.h

Tags

Discuss

Description

Dogeon (鴿子) likes everything to be rational, just like himself. He thinks that it is irrational that floating-point numbers in C/C++ are not accurate. So he decides to implement a class Rational to represent rational numbers. Since he prefer the class to be over-rational to use, you're asked to help him implement the following functions in an overloaded operator style.

1. Rational(int numerator, int denominator):
   a constructor that takes two integers numerator and denominator to represent the rational number.
2. Rational operator+(Rational const& b) const:
   an overloaded operator + that takes another Rational object b and returns a new Rational object that represents the sum of the two rational numbers.
3. Rational operator-(Rational const& b) const:
   an overloaded operator - that takes another Rational object b and returns a new Rational object that represents the subtraction of the two rational numbers.
4. Rational operator*(Rational const& b) const:
   an overloaded operator * that takes another Rational object b and returns a new Rational object that represents the multiplication of the two rational numbers.
5. Rational operator/(Rational const& b) const:
   an overloaded operator / that takes another Rational object b and returns a new Rational object that represents the division of the two rational numbers.
6. std::ostream& operator<<(std::ostream& os, Rational const& r):
   a friend function that overloads the << operator of std::ostream to output the rational number in the form numerator/denominator.

• This is a partial judge problem. You don't need to handle input. All you need to do is to implement the overloaded operators, the constructor, and the output function.
• This is a work of fiction. Any resemblance to actual persons, living or dead, or actual events is purely coincidental.

Input

The first line of the input contains an integer $N$, the number of expressions to be evaluated.

The next $N$ lines each contain the expression to be evaluated. Each expression contains two rational numbers $\frac{n_{i,1}}{d_{i,1}}, \frac{n_{i,2}}{d_{i,2}}$ and an operator $op_i$, separated by a space. The rational numbers are in the form numerator/denominator and the operator is one of +, -, *, /.

$N$
$n_{1,1}/d_{1,1} \quad op_1 \quad n_{1,2}/d_{1,2}$
$n_{2,1}/d_{2,1} \quad op_2 \quad n_{2,2}/d_{2,2}$
$\vdots$
$n_{N,1}/d_{N,1} \quad op_N \quad n_{N,2}/d_{N,2}$

Constraints

• $1 \leq N \leq 10^5$
• $-10^9 \leq n_{i,1}, d_{i,1}, n_{i,2}, d_{i,2} \leq 10^9$
• It is guaranteed that the denominator of the rational numbers is not 0.
• It is guaranteed that if operator is /, the second rational number is not 0.
• It is guaranteed that the simplest form of the result of each expression has a numerator and a denominator that are both within $[-10^9, 10^9]$.

Output

Each line of the output should contain the result of the corresponding expression in the simplest form $n_{i,3}/d_{i,3}$.

$\frac{n_{i,3}}{d_{i,3}} = (\frac{n_{i,1}}{d_{i,1}} \, \mathrm{op_i} \, \frac{n_{i,2}}{d_{i,2}})$, $d_{i,3} > 0$ and $\mathrm{gcd}(n_{i,3}, d_{i,3}) = 1$.

$n_{1,3}/d_{1,3}$
$n_{2,3}/d_{2,3}$
$\vdots$
$n_{N,3}/d_{N,3}$

Sample Input  Download

Sample Output  Download

Partial Judge Code

14277.cpp

Partial Judge Header

14277.h

Tags

Discuss