题目：
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 xi1, yi1, xi2, yi2, denoting that the i-th segment Dreamoon drew is a straight line segment between points (xi1, yi1) and (xi2, yi2).
- 1 ≤ N ≤ 2 × 103
- 0 ≤ xi1, yi1, xi2, yi2 ≤ 2 × 103
- 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
3
0 0 5 5
0 5 5 0
0 5 5 0
9
1
0 0 4 3
6
2
0 0 4 3
1 0 3 3
6
思路：
直接通过枚举y来判断直线经过哪些方格，vis标记下即可。
这题好像精度挺重要的。。。。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define MP make_pair 6 #define PB push_back 7 typedef long long LL; 8 typedef pair<int,int> PII; 9 const double eps=1e-8; 10 const double pi=acos(-1.0); 11 const int K=1e6+7; 12 const int mod=1e9+7; 13 14 int vis[3001][3001]; 15 struct Point 16 { 17 double x,y; 18 }; 19 void solve(void) 20 { 21 Point st,se; 22 scanf("%lf%lf%lf%lf",&st.x,&st.y,&se.x,&se.y); 23 if(fabs(st.x-se.x)<eps||fabs(st.y-se.y)<eps) return; 24 if(st.y>se.y) swap(st,se); 25 double k=(se.x-st.x)/(se.y-st.y),b=st.x-k*st.y; 26 double tmp; 27 if(k>0) 28 { 29 for(int i=se.y-1,mx,mi;i>=st.y;i--) 30 { 31 tmp=(i+1)*k+b; 32 mi=floor(i*k+b); 33 if(fabs(tmp-floor(tmp))<=eps)mx=max(0,(int)tmp-1); 34 else mx=(int)tmp; 35 if(mi<0) while(1); 36 while(mi<=mx) 37 vis[mi++][i]=1; 38 } 39 } 40 else 41 { 42 for(int i=st.y+1,mx,mi;i<=se.y;i++) 43 { 44 tmp=(i-1)*k+b; 45 mi=floor(i*k+b); 46 if(fabs(tmp-floor(tmp))<=eps)mx=max(0,(int)tmp-1); 47 else mx=(int)tmp; 48 if(mi<0) while(1); 49 while(mi<=mx) 50 vis[mi++][i-1]=1; 51 } 52 } 53 } 54 int main(void) 55 { 56 int n,cnt=0; 57 scanf("%d",&n); 58 for(int i=1;i<=n;i++) 59 solve(); 60 for(int i=0;i<2000;i++) 61 for(int j=0;j<2000;j++) 62 cnt+=vis[i][j]; 63 printf("%d ",cnt); 64 return 0; 65 }