2016-2017 National Taiwan University World Final Team Selection Contest C

题目：
Statements

Dreamoon likes algorithm competitions very much. But when he feels crazy because he cannot figure out any solution for any problem in a competition, he often draws many meaningless straight line segments on his calculation paper.

Dreamoon's calculation paper is special: it can be imagined as the plane with Cartesian coordinate system with range [0, 2000] × [0, 2000] for the coordinates. The grid lines are all lines of the form x = c or y = c for every integer c between 0 and 2000, inclusive. So, the grid contains 2000 × 2000 squares.

Now, Dreamoon wonders how many grid squares are crossed by at least one of the lines he drew. Please help Dreamoon find the answer. Note that, to cross a square, a segment must contain an interior point of the square.

Input

The first line of input contains an integer N denoting the number of lines Dreamoon draw. The i-th line of following N lines contains four integers x_i1, y_i1, x_i2, y_i2, denoting that the i-th segment Dreamoon drew is a straight line segment between points (x_i1, y_i1) and (x_i2, y_i2).

1 ≤ N ≤ 2 × 10³
0 ≤ x_i1, y_i1, x_i2, y_i2 ≤ 2 × 10³
the lengths of all line segments in input are non-zero

Output

Output one integer on a single line: how many grid squares are crossed by at least one of the line segments which Dreamoon drew.

Example

Input

Output

Input

1
0 0 4 3

Output

Input

2
0 0 4 3
1 0 3 3

Output

6

思路：
　　直接通过枚举y来判断直线经过哪些方格，vis标记下即可。
　　这题好像精度挺重要的。。。。

 #include <bits/stdc++.h>

 using namespace std;

 #define MP make_pair

 #define PB push_back

 typedef long long LL;

 typedef pair<int,int> PII;

 const double eps=1e-;

 const double pi=acos(-1.0);

 const int K=1e6+;

 const int mod=1e9+;

 int vis[][];

 struct Point

 {

     double x,y;

 };

 void solve(void)

 {

     Point st,se;

     scanf("%lf%lf%lf%lf",&st.x,&st.y,&se.x,&se.y);

     if(fabs(st.x-se.x)<eps||fabs(st.y-se.y)<eps) return;

     if(st.y>se.y) swap(st,se);

     double k=(se.x-st.x)/(se.y-st.y),b=st.x-k*st.y;

     double tmp;

     if(k>)

     {

         for(int i=se.y-,mx,mi;i>=st.y;i--)

         {

             tmp=(i+)*k+b;

             mi=floor(i*k+b);

             if(fabs(tmp-floor(tmp))<=eps)mx=max(,(int)tmp-);

             else mx=(int)tmp;

             if(mi<) while();

             while(mi<=mx)

                 vis[mi++][i]=;

         }

     }

     else

     {

         for(int i=st.y+,mx,mi;i<=se.y;i++)

         {

             tmp=(i-)*k+b;

             mi=floor(i*k+b);

             if(fabs(tmp-floor(tmp))<=eps)mx=max(,(int)tmp-);

             else mx=(int)tmp;

             if(mi<) while();

             while(mi<=mx)

                 vis[mi++][i-]=;

         }

     }

 }

 int main(void)

 {

     int n,cnt=;

     scanf("%d",&n);

     for(int i=;i<=n;i++)

         solve();

     for(int i=;i<;i++)

     for(int j=;j<;j++)

         cnt+=vis[i][j];

     printf("%d\n",cnt);

     return ;

 }

巴特西

2016-2017 National Taiwan University World Final Team Selection Contest C - Crazy Dreamoon

最新文章

热门文章