hdu 2528 Area，hdu2528area

hdu 2528 Area，hdu2528area

2014-07-30

http://acm.hdu.edu.cn/showproblem.php?pid=2528
解題思路：
　　求多邊形被一條直線分成兩部分的面積分別是多少。因為題目給的直線一定能把多邊形分成兩部分，所以就不用考慮多邊形是否與直線相交。直接求問題。
　　
　　將多邊形的每一條邊與直線判斷是否相交。若相交，就從這點開始計算面積，直到判斷到下一個邊與直線相交的點。這之間的面積求出來為area2。
　　area1為多邊形的總面積。多邊形被直線分成的另外一部分面積 = area1 - area2

　　有一個特殊的情況：當直線與多邊形的頂點相交時，應該考慮下如何處理

  1 #include<cmath>
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<algorithm>
  5 using namespace std;
  6 
  7 #define MAXN 30
  8 #define EPS 0.00000001
  9 
 10 int dcmp(double x){
 11     if(fabs(x) < EPS)
 12         return 0;
 13     return x < 0 ? -1 : 1;
 14 }
 15 
 16 struct Point{
 17     double x, y;
 18     Point(double x = 0, double y = 0): x(x), y(y) {}
 19 
 20     bool operator != (const Point & other){
 21         return dcmp(x - other.x) != 0 || (dcmp(x - other.x) == 0 && dcmp(y - other.y) != 0);
 22     }
 23 };
 24 
 25 struct Line{
 26     Point A, B;
 27     //Line(Point A = Point(0, 0), Point B = Point(0, 0)): A(A), B(B){}
 28 };
 29 
 30 typedef Point Vector;
 31 
 32 Vector operator + (Vector A, Vector B){
 33     return Vector(A.x + B.x, A.y + B.y);
 34 }
 35 
 36 Vector operator - (Point A, Point B){
 37     return Vector(A.x - B.x, A.y - B.y);
 38 }
 39 
 40 Vector operator * (Vector A, double d){
 41     return Vector(A.x * d, A.y * d);
 42 }
 43 
 44 Vector operator / (Vector A, double d){
 45     return Vector(A.x / d, A.y / d);
 46 }
 47 
 48 double dot(Vector A, Vector B){//點乘
 49     return A.x * B.x + A.y * B.y;
 50 }
 51 
 52 double cross(Vector A, Vector B){//叉乘
 53     return A.x * B.y - A.y * B.x;
 54 }
 55 
 56 int n;
 57 Point p[MAXN];
 58 Line line;
 59 
 60 bool input(){
 61     scanf("%d", &n );
 62     if(!n){
 63         return false;
 64     }
 65     for(int i = 0; i < n; i++ ){
 66         scanf("%lf%lf", &p[i].x, &p[i].y );
 67     }
 68     scanf("%lf%lf%lf%lf", &line.A.x, &line.A.y, &line.B.x, &line.B.y );
 69     return true;
 70 }
 71 
 72 double polygon_area(){//求多邊形面積
 73     double area = 0;
 74     for(int i = 1; i < n - 1; i++ ){
 75         area += cross(p[i] - p[0], p[i + 1] - p[0]);
 76     }
 77     return fabs(area) * 0.5;
 78 }
 79 
 80 bool line_segment_intersect(Line L, Point A, Point B, Point &P){//直線和線段相交
 81     Vector a = A - L.B, b = L.A - L.B, c = B - L.B;
 82     if(dcmp(cross(a, b)) * dcmp(cross(b, c)) >= 0){//若直線和線段相交 求出交點 《算法入門經典訓練之南》上的公式
 83         Vector u = L.A - A;
 84         double t = cross(A - B, u) / cross(b, A - B);
 85         P = L.A + b * t;
 86         return true;
 87     }
 88     return false;
 89 }
 90 
 91 void solve(){
 92     int flag = 0;
 93     double area1 = polygon_area(), area2 = 0;//area1算出多邊形總面積
 94     Point P, T;
 95 
 96     p[n] = p[0];
 97     for(int i = 0; i < n; i++ ){
 98         if(flag == 0 && line_segment_intersect(line, p[i], p[i + 1], P)){//第一次相交點
 99             area2 += cross(P, p[i + 1]);
100             flag++;
101         }else if(flag == 1 && line_segment_intersect(line, p[i], p[i + 1], T) && P != T){//第二次相交點
102             area2 += cross(p[i], T);
103             area2 += cross(T, P);
104             flag++;
105             break;
106         }else if(flag == 1){
107             area2 += cross(p[i], p[i + 1]);
108         }
109     }
110     area2 = fabs(area2) * 0.5;
111     area1 -= area2;//area1 獲取多邊形另外一半的面積
112     if(area1 < area2){//規定大面積在前面 輸出
113         swap(area1, area2);
114     }
115     printf("%.0lf %.0lf\n", area1, area2);
116 }
117 
118 int main(){
119     //freopen("data.in", "r", stdin );
120     while(input()){
121         solve();
122     }
123     return 0;
124 }

幫我講解下這題（HDU）

赤裸的BFS，但是要注意下標記，得用x，y，t三維標記。因為有些坐標有經過多次來重置炸彈。。
貼下我的代碼。。
#include<stdio.h>
struct queue
{
int x;
int y;
int time;
int t;
}a[200000];
int si,sj,ei,ej,n,m,d[4][2]={-1,0,1,0,0,-1,0,1};
int map[10][10],hash[10][10][10];
int bfs()
{
int i,x1,y1,t1,head,tail;
a[0].x=si;
a[0].y=sj;
a[0].time=0;
a[0].t=6;
head=0;tail=1;
while(head<tail)
{
// printf("\n%d %d %d %d\n",a[head].x,a[head].y,a[head].time,a[head].t);
// printf("-----------------------------------\n");

for(i=0;i<4;i++)
{
if(a[head].t<2)
break;
x1=a[head].x+d[i][0];
y1=a[head].y+d[i][1];
if(map[x1][y1]==4)
t1=6;
else
t1=a[head].t-1;
if(hash[x1][y1][t1])
continue;
if(x1<0||x1>=n||y1<0||y1>=m)
continue;
if(map[x1][y1]==0)
continue;
a[tail].x=x1;
a[tail].y=y1;
a[tail].t=t1;
a[tail].time=a[head].time+1;
hash[x1][y1][a[tail].t]=1; //注意這裡的標記。
// printf("%d %d %d %d\n",a[tail].x,a[tail].y,a[tail].time,a[tail].t);
if(x1==ei&&y1==ej)
return (a[head].time+1);
tail++;
}
// printf("\n");
head++;
}
return 0;
}......余下全文>>
 

小弟大一學ACM，推薦幾本書，

我是一個大三的學生！自大學一年級，我開始做的ACM，我覺得你可能有資格在杭州新華下載了一套杭電ACM課件
PPT，你將有很大的提高！有什麼不明白在網上搜索！現在有很多的在線答疑！我覺得網上資源太豐富。比一本好書，而不是為了金錢！你就會快速的得到提高，對細節的關注，恆功率，以幫助您確定問題是否糾正你做，有時你認為你自己的問題，正確的，但不完全。杭電可以幫你了解一下。事實上，游戲的時間，很多的答案認為是正確的，但筆者不上去，細節決定成敗。一個良好的開端，從大一在杭州新華有權這樣做。你會成為高手！