Shape of HDU
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4407 Accepted Submission(s): 1957
Problem Description
話說上回講到海東集團推選老總的事情,最終的結果是XHD以微弱優勢當選,從此以後,“徐隊”的稱呼逐漸被“徐總”所取代,海東集團(HDU)也算是名副其實了。
創業是需要地盤的,HDU向錢江肉絲高新技術開發區申請一塊用地,很快得到了批復,據說這是因為他們公司研發的“海東牌”老鼠藥科技含量很高,預期將占全球一半以上的市場。政府劃撥的這塊用地是一個多邊形,為了描述它,我們用逆時針方向的頂點序列來表示,我們很想了解這塊地的基本情況,現在請你編程判斷HDU的用地是凸多邊形還是凹多邊形呢?
Input
輸入包含多組測試數據,每組數據占2行,首先一行是一個整數n,表示多邊形頂點的個數,然後一行是2×n個整數,表示逆時針順序的n個頂點的坐標(xi,yi),n為0的時候結束輸入。
Output
對於每個測試實例,如果地塊的形狀為凸多邊形,請輸出“convex”,否則輸出”concave”,每個實例的輸出占一行。
Sample Input
4
0 0 1 0 1 1 0 1
0
Sample Output
convex
海東集團終於順利成立了!後面的路,他們會順順利利嗎?
欲知後事如何,且聽下回分解——
Author
lcy
Source
ACM程序設計_期末考試(時間已定!!)
import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner input=new Scanner(System.in); int n; while((n=input.nextInt())!=0){ Point f[]=new Point[n+5]; for(int i=0;i<n;i++){ int a=input.nextInt(); int b=input.nextInt(); f[i]=new Point(a,b); } f[n]=new Point(f[0].x,f[0].y); f[n+1]=new Point(f[1].x,f[1].y); boolean ok=true; for(int i=0;i<n;i++){ Point a=new Point(f[i+1].x-f[i].x,f[i+1].y-f[i].y); Point b=new Point(f[i+2].x-f[i+1].x,f[i+2].y-f[i+1].y); int ans=a.x*b.y-b.x*a.y; if(ans<0){ ok=false; break; } } if(ok) System.out.println("convex"); else System.out.println("concave"); } } } class Point{ int x,y; Point(int x,int y){ this.x=x; this.y=y; } // Point(){} }
/* * 8913013 2013-08-12 11:26:28 Accepted 2108 140MS 2920K 1040 B Java zhangyi */ import java.util.Scanner; public class MM {//郭思慧 /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner input=new Scanner(System.in); while(true){ int n=input.nextInt(); if(n==0) break; Shape[] arr=new Shape[n+1]; for(int i=1;i<=n;i++){ arr[i]=new Shape(); } boolean flag=true; for(int i=1;i<=n;i++){ arr[i].x=input.nextInt(); arr[i].y=input.nextInt(); } int a,b,c; int x1,y1,x2,y2; for(int i=1;i<=n;i++){ a=i; b=i+1; c=i+2; if(a==n-1) c=1; if(a==n){ b=1; c=2; } x1=arr[a].x-arr[b].x; y1=arr[a].y-arr[b].y; x2=arr[c].x-arr[b].x; y2=arr[c].y-arr[b].y; if(x1*y2-x2*y1>0){ flag=false; break; } }//for if(flag==true) System.out.println("convex"); else System.out.println("concave"); } } } class Shape{ int x=0; int y=0; Shape(int x,int y){ this.x=x; this.y=y; } Shape(){} }