http://172.20.6.3/Problem_Show.asp?id=1535
整体来说是道水题，但是穿过点的判定把我坑得wa了两次,考场上这可是40分的水分啊啊啊。
开始的错误想法：排序后向上扫一遍，通过边就转换加或不加这一段的状态，通过点就不转换。
错误想法没有考虑到折点而非转点的情况。
正确想法与错误的只有点的判定不同：点的判定是如果这个点连接的两条边是在穿越线的一侧，则通过这点后加或不加的状态不变，否则转换。
还是逻辑太弱。
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define lc x*2 8 #define rc x*2+1 9 using namespace std; 10 const int maxn=110; 11 int n,x,y; 12 int a[maxn]={}; 13 int b[maxn]={}; 14 struct wtf{ 15 double y; 16 bool f; 17 }e[maxn]; 18 int tot=0; 19 bool mmp(wtf xx,wtf yy){ 20 return xx.y<yy.y; 21 } 22 int main(){ 23 scanf("%d",&n); 24 for(int i=1;i<=n;i++){ 25 scanf("%d%d",&a[i],&b[i]); 26 }a[0]=a[n];b[0]=b[n]; 27 scanf("%d%d",&x,&y);int x1,x2,y1,y2; 28 for(int i=1;i<=n;i++){ 29 if(a[i]==x){ 30 e[++tot].y=b[i];e[tot].f=0; 31 if((a[i-1]-a[i])*(a[i+1]-a[i])>0) e[tot].f=1; 32 } 33 if((a[i]-x)*(a[i-1]-x)<0){ 34 if(a[i]>a[i-1]){x1=a[i-1],x2=a[i],y1=b[i-1],y2=b[i];} 35 else {x1=a[i],x2=a[i-1],y1=b[i],y2=b[i-1];} 36 e[++tot].y=double(y2-y1)/(x2-x1)*(x-x1)+y1; 37 e[tot].f=0; 38 } 39 } 40 sort(e+1,e+1+tot,mmp); 41 double cnt=0,z;int f=1; 42 if(e[1].f)f=0; 43 for(int i=2;i<=tot;i++){ 44 if(f&&e[i].y>y){ 45 if(y>e[i-1].y)z=y; 46 else z=e[i-1].y; 47 cnt+=e[i].y-z; 48 } 49 if(!e[i].f)f=f^1; 50 51 }int ans=cnt; 52 printf("%d ",ans); 53 return 0; 54 }