Category Archives: poj

http://poj.org/problem?id=1687 #include<iostream> #include"math.h" using namespace std; long x[50],y[50]; inline long cheng(int a,int b,int c) {return (x[a]-x[b])*(y[a]-y[c])-(x[a]-x[c])*(y[a]-y[b]);} int main() {int t,n,m,p[50],h,key,i,j,l;char s[50];long an,anb; cin>>t; for(;t>0;t–) {cin>>n; for(i=0;i<n;i++) cin>>x[i]>>y[i]; cin>>m;key=0;anb=0; for(l=0;l<m;l++) {cin>>h; for(i=0;i<h;i++){cin>>p[i];p[i]–;} an=0; for(i=1;i<h-1;i++) { an+=cheng(p[0],p[i],p[i+1]); } // cout<<":::"<<an<<endl; if(abs(an)>anb){anb=abs(an);key=l+1; } … Continue reading →

http://poj.org/problem?id=1686 //* @author: import java.util.Scanner; import javax.script.ScriptEngine; import javax.script.ScriptEngineManager; import javax.script.ScriptException; public class Main{ ScriptEngineManager factory = new ScriptEngineManager(); ScriptEngine engine = factory.getEngineByName("JavaScript"); Scanner cin=new Scanner(System.in); int[] num=new int[60]; void init() { for(int i=1;i< 59;i++) num[i]=i+9997; } void solve() throws … Continue reading →

http://poj.org/problem?id=1685 #include<iostream> #include"math.h" #include"stdio.h" using namespace std; double x[60][2],y[60][2],xs,ys,xt,yt; double best1[62][2],best2[62][2],len[62]; int color[60],cl,c[62]; inline double jl(double a,double c,double b,double d) {return sqrt((a-b)*(a-b)+(c-d)*(c-d));} int main() {int t,i,j,k,n;double ss,tt; cin>>t; for(;t>0;t–) {cin>>xs>>ys>>xt>>yt; cin>>cl; for(i=0;i<cl;i++)cin>>color[i]; cin>>n; for(i=0;i<n;i++){cin>>x[i][0]>>y[i][0]>>x[i][1]>>y[i][1]>>c[i]; len[i]=jl(x[i][0],y[i][0],x[i][1],y[i][1]);} for(i=0;i<n;i++) if(c[i]==color[0]){best1[i][0]=jl(xs,ys,x[i][0],y[i][0])+len[i]; best1[i][1]=jl(xs,ys,x[i][1],y[i][1])+len[i];} else best1[i][0]=best1[i][1]=999999999999; … Continue reading →

http://poj.org/problem?id=1683 #include<iostream> using namespace std; int h[50][8],n,m; char obj[8][8]; int sign[50][50]; int alive[50]; int can(int i,int j) {int k; for(k=0;k<n;k++) if(h[i][k]*h[j][k]>0)break; if(k==n)return 1; else return 0; } void merage(int a,int b) {int i; for(i=0;i<n;i++)h[a][i]+=h[b][i]; for(i=0;i<n*m;i++){sign[a][i]+=sign[b][i];sign[i][a]+=sign[i][b];} alive[b]=-a; } int main() {int … Continue reading →

http://poj.org/problem?id=1681 //* @author: import java.util.*; public class Main { static Scanner in = new Scanner(System.in); static char[][] board;//���ڱ����ʼ״̬ static boolean[][] map;//ǽ�ڵ�״̬ static int cnt;//Ϳ��Ĵ��� static void click(int x, int y) {//Ϳ��x,y)���ĸ��� ++cnt; map[x][y] = !map[x][y]; if(x-1>=0) map[x-1][y] = !map[x-1][y];//����ĸ��� if(y-1>=0) … Continue reading →

http://poj.org/problem?id=1679 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; class Edge{ int u,v,disten; void set(int u,int v,int disten){ this.u = u; this.v = v; this.disten = disten; } } interface MST{ int N = 100+2,BIG = 1000000000; int getMST(int op); } … Continue reading →

http://poj.org/problem?id=1677 //* @author /** * pku 1677 Girls’ Day * Memory: 3524K Time: 172MS * Language: Java Result: Accepted * @Author conanhjj */ import java.util.*; public class Main { static Scanner in = new Scanner(System.in); static int g,w; static String[] … Continue reading →

http://poj.org/problem?id=1676 //* @author: 82638882@163.com import java.io.*; public class Main { public static void main(String[] args) throws IOException { InputStreamReader is=new InputStreamReader(System.in); BufferedReader in=new BufferedReader(is); int a=Integer.parseInt(in.readLine()); int[] N=new int[]{ 119,36,93,109,46,107,123,37,127,111}; while((a–)!=0) { int[] Num1=new int[4]; int[] Num2=new int[4]; String line=in.readLine(); … Continue reading →

http://poj.org/problem?id=1675 /* @author:����acmilan_fan@yahoo.cn */ import java.io.*; public class Main { static double A = Math.PI*2/3; public static void main(String[] args)throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s = br.readLine(); String[] ss; int num = Integer.parseInt(s); int x1, y1, … Continue reading →

http://poj.org/problem?id=1674 //* @author: 82638882@163.com import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { InputStreamReader is=new InputStreamReader(System.in); BufferedReader in=new BufferedReader(is); String[] ss; int a=Integer.parseInt(in.readLine()); HashSet< Integer> hs=new HashSet< Integer>(); while((a–)!=0) { int b=Integer.parseInt(in.readLine()); ss=in.readLine().split(" … Continue reading →

http://poj.org/problem?id=1671 import java.util.*; public class Main{ static double dp[][]=new double[51][51]; static { dp[1][1]=1; for (int i=2;i<=50;i++) for(int j=1;j<=50;j++) dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j; } public static void main(String args[]){ Scanner sc=new Scanner(System.in); while (sc.hasNext()) { int n=sc.nextInt(); if(n==0) break; double ans=0; for (int i=1;i<=n;i++) … Continue reading →

http://poj.org/problem?id=1666 //* @author ������&lt;hongxp11@163.com&gt; import java.util.Scanner; public class Main { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); while (true) { int student = in.nextInt(); if (0 … Continue reading →

http://poj.org/problem?id=1664 import java.io.BufferedInputStream; import java.util.Scanner; /** * *poj1664 * f(m, n) = f(m-n, n) + f(m, n-1) * f(m, n): ��m��ƻ��ŵ�n�������еķ����� * f(m, n-1): ��m��ƻ��ŵ�n-1�������еķ�����(����������һ�������) * f(m-n, n): ��m��ƻ��ŵ�n��������,����ÿ�������ж���ƻ��(����n���4,��m-n��ź���,Ȼ��ÿ�����ӷ�һ��) * @author NC */ public class Main { public static void … Continue reading →

http://poj.org/problem?id=1663 //* @author mekarlos@gmail.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in)); int n=new Integer(stdin.readLine()); StringTokenizer tokens; int x,y; for(int i=0;i< n;i++){ tokens=new StringTokenizer(stdin.readLine()); … Continue reading →

http://poj.org/problem?id=1661 import java.util.Arrays; import java.util.Scanner; /** * POJ1661 * @author Bruce * */ class Board implements Comparable<Board>{ int lx; int rx; int h; public Board(int x,int y,int h){ this.lx = x; this.rx = y; this.h = h; } public int … Continue reading →

http://poj.org/problem?id=1659 //* @author: 82638882@163.com import java.io.*; import java.util.*; public class Main { static int[][] p; static ri[] arr; public static void main(String[] args) throws IOException { InputStreamReader is=new InputStreamReader(System.in); BufferedReader in=new BufferedReader(is); int n=Integer.parseInt(in.readLine()); while((n–)!=0) { int m=Integer.parseInt(in.readLine()); p=new int[m][m]; … Continue reading →

http://poj.org/problem?id=1658 //* @author ������&lt;hongxp11@163.com&gt; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); for(int i = 0; i < n; i++) { int one = in.nextInt(); int two … Continue reading →

http://poj.org/problem?id=1657 #include <stdio.h> #include <math.h> int main() { int t; scanf("%d", &t); char c1, c2; int x1, y1, x2, y2; int w, h, c, x; while (t–) { getchar(); scanf("%c%d %c%d", &c1, &y1, &c2, &y2); x1 = c1 – ‘a’ … Continue reading →

http://poj.org/problem?id=1656 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int num = in.nextInt(); int[][] grids = new int[101][101]; for(int i = 0; i< num; i++) { String color = in.next(); int … Continue reading →

http://poj.org/problem?id=1655 #include<iostream> using namespace std; typedef struct edge {int a; struct edge *p; }edge; edge *a[21000]; int s[21000]; int b[21000]; int f[21000]; int fr[21000]; int go; void find(int from,int to) {edge *p; p=a[to];fr[to]=from; while(p) {if(p->a==from){p=p->p;continue;} find(to,p->a);p=p->p; } f[go–]=to; } int … Continue reading →

http://poj.org/problem?id=1654 /* @author: */ import java.util.*; public class Main { static long get_Area(long x1,long y1, long x2,long y2) { return x1*y2-x2*y1; } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int move[][]={{0,0},{1,-1},{1,0},{1,1},{0,-1},{0,0},{0,1},{-1,-1},{-1,0},{-1,1}}; int d,ncase; long x0,y0,newx,newy,area; ncase=sc.nextInt(); String … Continue reading →

http://poj.org/problem?id=1651 //* @author: 82638882@163.com import java.io.*; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { InputStreamReader is=new InputStreamReader(System.in); BufferedReader in=new BufferedReader(is); int a=Integer.parseInt(in.readLine()); int[] arr=new int[a]; String[] ss=in.readLine().split(" "); for(int i=0;i< a;i++) arr[i]=Integer.parseInt(ss[i]); int[][] gra=new int[a][a]; … Continue reading →

http://poj.org/problem?id=1650 /* @author: */ import java.util.Scanner; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); double a; int d; a=sc.nextDouble(); d=sc.nextInt(); double ans; double min=a; int v1=0,v2=0,m=1,n=1; while(m<=d&&n<=d) { ans=m*1.0/n*1.0; if(ans>=a) { if(min>ans-a) { min=ans-a; v1=m; v2=n; } … Continue reading →

http://poj.org/problem?id=1648 #include<stdio.h> #include<string.h> #include<stdlib.h> #include<string.h> #include<math.h> #define INF 30000 #define NMAX 13 float N,E,W; double gety(double x) { return (E-W)/N*x+W; } void solve() { int i,j; int sum=0; double(y); for(i=0;i<N;i++) { for(j=0;j<N;j++) { for(int p=0;p<2;p++) { y=gety(i+p); if(y>=j&&y<=j+1) { sum++; … Continue reading →

http://poj.org/problem?id=1639 //* @author import java.util.*; import java.io.*; import java.util.concurrent.*; public class Main { private static class UFSets { UFSets(int l) { s = new int[l]; for(int i=0; i!=l; ++i) s[i] = i; } void union(int x, int y) { s[find(x)] … Continue reading →

http://poj.org/problem?id=1637 //* @author import java.util.*; import java.util.concurrent.ArrayBlockingQueue; public class Main { static int N = 205; static int [] degin, degout, deg, pre; static int [][] cap; private static int maxflow(int s, int t, int size) { Queue<Integer> que = … Continue reading →

http://poj.org/problem?id=1633 //* @author:alpc12 import java.math.BigInteger; import java.util.Scanner; public class Main { BigInteger[][] dp = new BigInteger[51][51]; BigInteger go(int n, int y) { if (y == 1) return BigInteger.ONE; if (n < y || y < 1) return BigInteger.ZERO; if(dp[n][y] != … Continue reading →

http://poj.org/problem?id=1631 #include <stdio.h> #include <algorithm> using namespace std; int a[40000], n; int ans[40000]; int id[40000], m; bool cmp( int s1,int s2 ) { return a[s1] < a[s2]; } int main() { int i, j, s; int cas; scanf( "%d", &cas … Continue reading →

http://poj.org/problem?id=1630 #include<iostream> using namespace std; struct point {int x,y;}; long cheng(point a,point b,point c) {return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);} long dcheng(point a,point b,point c) {return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)+(c.y-a.y);} point p[10000]; int n,k[32],begin[32],end[32],m; void init() {int i,h=0;char c; cin>>n; for(i=0;i<=n;i++) {begin[i]=h; while(cin.peek()!=’#’) {cin>>p[h].x>>c; cin>>p[h++].y>>c; } cin.get(); … Continue reading →

http://poj.org/problem?id=1628 #include <stdio.h> #include <algorithm> using namespace std; __int64 p[210],q[210]; inline int geti( char c ) { if( c <= ‘Z’ && c >= ‘A’ ) return c – ‘A’ + 26; else return c – ‘a’; } int n, … Continue reading →

http://poj.org/problem?id=1617 /* @author:����acmilan_fan@yahoo.cn */ import java.io.*; import java.util.*; public class Main { public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s; String ciphertext; int codesize; int textrow; int colnum; StringBuilder sb; while((s=br.readLine())!=null&&!s.equals("THEEND")){ //length of the … Continue reading →

http://poj.org/problem?id=1615 #include"iostream" #include"stdlib.h" #include"memory.h" //#include"time.h" using namespace std; long m[5][100],len[5],n,total,answer; /////////////////////////// long cas; /////////////////////////// void init() { n=5;total=0; int i,j; for(i=0;i<n;i++) { len[i]=80; for(j=0;j<len[i];j++) { m[i][j]=rand()%201-100; total+=m[i][j]; } } } void init1() { n=0;total=0; do { len[n]=0; do { cin>>m[n][len[n]++]; … Continue reading →

http://poj.org/problem?id=1612 #include<iostream> using namespace std; int dis[50][50],n; void init() { char c; int i,j,k; cin>>n; for(i=0;i<n;i++) { for(j=0;j<n;j++) dis[i][j]=9999; dis[i][i]=0; } for(i=0;i<n;i++) { cin.get(c); while(cin.peek()!=’n’) { cin>>j; dis[i][j-1]=1; dis[j-1][i]=1; } } for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) if(dis[i][k]<9999&&dis[k][j]<9999&&dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j]; } void doit() { … Continue reading →

http://poj.org/problem?id=1611 import java.util.Arrays; import java.util.Scanner; public class Main { static int[] student; static int[] ans; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); int m = sc.nextInt(); if (n == … Continue reading →

http://poj.org/problem?id=1609 //* @author: ccQ.SuperSupper import java.io.*; import java.util.*; public class Main { static final int N = 100+10; static int point[][] = new int[N][N],DP[][] = new int[N][N]; static void init(){ for(int i=0;i< N;++i) for(int j=0;j< N;++j) point[i][j] = 0; } … Continue reading →

http://poj.org/problem?id=1607 //* @author popop0p0popo import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws Exception{ Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in))); System.out.printf("Cards Overhangn"); int n; double d; while (scanner.hasNext()){ n=scanner.nextInt(); d=0; for (int i=1;i<=n ;i++ ){ d=d+1.0/(2*i); } … Continue reading →

http://poj.org/problem?id=1604 //* @author: 82638882@163.com import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int[] b2=new int[]{6,2,4,8}; int[] b3=new int[]{1,3,9,7}; int[] b7=new int[]{1,7,9,3}; int[] b9=new int[]{1,9,1,9}; while(in.hasNext()) { int n=in.nextInt(); int e,a2=0,a3=0,a5=0,a7=0,a9=0; e=n;while((e=e/2)!=0) a2+=e; e=n;while((e=e/5)!=0) … Continue reading →

http://poj.org/problem?id=1603 //* @author: 82638882@163.com import java.util.Scanner; public class Main { static int[][] w=new int[21][21]; static final int n=20; public static void main(String[] args) { Scanner in=new Scanner(System.in); int cnt=0; while(in.hasNext()) { cnt++; for(int i=0;i< n;i++) for(int j=0;j< n;j++) w[i][j]=9999999; for(int … Continue reading →

http://poj.org/problem?id=1598 //* @author popop0p0popo import java.util.*; import java.io.*; public class Main{ public static void main(String[] args){ Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in))); String[] kws; String[] exs,exsk; int[] kn; String fl; int n,m,max; int index=1; while (scanner.hasNext()){ fl=scanner.nextLine(); String[] t=fl.split(" "); n=Integer.parseInt(t[0]); … Continue reading →

http://poj.org/problem?id=1597 //* @author mekarlos@gmail.com import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int s=0,m=0,ac=0; boolean[] bands; boolean flaj; while(scan.hasNext()){ s=scan.nextInt(); m=scan.nextInt(); bands=new boolean[m+1]; flaj=true; ac=0; for(int i=0;i< m;i++){ if(bands[ac]){ flaj=false; break; } bands[ac]=true; … Continue reading →

http://poj.org/problem?id=1595 //* @author: 82638882@163.com import java.util.Scanner; public class Main { public static void main(String[] args) { int[] arr=new int[]{ 1,2,3,5,7,11,13,17,19,23,29,31,37,41, 43,47,53,59,61,67,71,73,79,83,89,97,101,103,107, 109,113,127,131,137,139,149,151,157,163,167,173,179,181,191, 193,197,199,211,223,227,229,233,239,241,251,257,263,269,271, 277,281,283,293,307,311,313,317,331,337,347,349,353,359,367, 373,379,383,389,397,401,409,419,421,431,433,439,443,449,457, 461,463,467,479,487,491,499,503,509,521,523,541,547,557,563, 569,571,577,587,593,599,601,607,613,617,619,631,641,643,647, 653,659,661,673,677,683,691,701,709,719,727,733,739,743,751, 757,761,769,773,787,797,809,811,821,823,827,829,839,853,857, 859,863,877,881,883,887,907,911,919,929,937,941,947,953,967, 971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061, 1063,1069,1087,1091,1093,1097 }; Scanner in=new Scanner(System.in); while(in.hasNext()) { int a=in.nextInt(); … Continue reading →

http://poj.org/problem?id=1591 //* @author: SmilingWang import java.util.*; public class Main{ public static void main(String[] args){ LinkedList< Integer> list; Scanner in = new Scanner(System.in); int n; int left; int i, j; int count = 1; while(in.hasNext()){ n = in.nextInt(); left = in.nextInt(); … Continue reading →

http://poj.org/problem?id=1590 //* @author: <strong>Yeming&nbsp;Hu</strong>&quot;cslittleye@gmail.com&quot; import java.util.Scanner; import java.util.Map; import java.util.HashMap; import java.io.BufferedInputStream; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(new BufferedInputStream(System.in)); Map<Character,Character> map = new HashMap<Character,Character>(); map.put(‘A’,’A’); map.put(‘E’,’3′); map.put(‘H’,’H’); map.put(‘I’,’I’); map.put(‘J’,’L’); map.put(‘L’,’J’); map.put(‘M’,’M’); … Continue reading →

http://poj.org/problem?id=1581 //* @author mekarlos@gmail.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in)); int n=new Integer(stdin.readLine()); String nombre="",winner=""; int sub,pena,solved,time; int maxsolved=0,mintime=0; StringTokenizer tokens; for(int … Continue reading →

http://poj.org/problem?id=1580 //* @author: 82638882@163.com import java.util.*; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); while(true) { String s1=in.next(); if(s1.equals("-1"))break; String s2=in.next(); int max=0; for(int i=0;i< s1.length();i++) { int count =0; for(int j=0;j< s2.length();j++) { boolean … Continue reading →

http://poj.org/problem?id=1577 //* @author: SmilingWang import java.util.*; public class Main { public static void main(String[] args){ Scanner in =new Scanner(System.in); BinarySearchTree< Character> bt = new BinarySearchTree< Character>(); boolean stop = false; while(true){ String input = in.next(); LinkedList< String> list = new … Continue reading →

http://poj.org/problem?id=1576 /* @author:����acmilan_fan@yahoo.cn */ import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s,board; String[] ss; int n; int[] p; boolean flag=false; while((s=br.readLine())!=null&&!s.startsWith("0")){ ss=s.split(" ",3); p=new int[parseInt(ss[0])]; … Continue reading →

http://poj.org/problem?id=1575 //* @author: 82638882@163.com import java.io.*; public class Main { static int[][] sorce; public static void main(String[] args) throws IOException { InputStreamReader is=new InputStreamReader(System.in); BufferedReader in=new BufferedReader(is); while(true) { String s=in.readLine(); if(s.equals("end"))break; boolean bb=true,b1=false,b2; for(int i=0;i< s.length();i++) { if(isv(s.charAt(i))) { … Continue reading →

http://poj.org/problem?id=1574 /* @author: */ import java.util.*; public class Main { private int x[]; private int y[]; private int z[]; private int a[]=new int[7],b[]=new int[7],c[]=new int[7],ax[]=new int[7],use[]=new int[7]; private int max; public Main(int x[],int y[],int z[]){ this.x=x; this.y=y; this.z=z; max=0; for(int … Continue reading →

http://poj.org/problem?id=1566 //* @author: <strong>Yeming&nbsp;Hu</strong>&quot;cslittleye@gmail.com&quot; import java.util.*; import java.io.BufferedInputStream; public class Main { public static int[] numbers = {5,7,5}; public static void main(String[] args) { Scanner sc = new Scanner(new BufferedInputStream(System.in)); sc.useDelimiter("n"); while(true) { String line = sc.next(); line = line.trim(); … Continue reading →